Leetcode 101. Symmetric Tree 化用深度搜索

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

    1
   / \
  2   2
 / \ / \
3  4 4  3

But the following [1,2,2,null,3,null,3] is not:

    1
   / \
  2   2
   \   \
   3    3

化用深度搜索

本题既可以用BFS，也可以用DFS。BFS是按层次遍历，要求每个层次中的节点都是对称的。DFS是递归遍历，要求相互对称的节点是等价的。根据我们之前的规律，如果DFS在功能上等价的话，往往效率更快，代码更加简洁有力。

DFS(>94.36%)

class Solution {

    private boolean dfs(TreeNode node1, TreeNode node2){
        if (node1==null && node2==null) return true;
        if (node1==null || node2==null) return false;
        if (node1.val!=node2.val) return false;
        if (!dfs(node1.left,node2.right)) return false;
        if (!dfs(node1.right,node2.left)) return false;
        return true;
    }

    public boolean isSymmetric(TreeNode root) {
        if (root==null) return true;
        return dfs(root.left,root.right);
    }
}