LeetCode-Symmetric Tree

上一题Same Tree的思路肯定是没法用了，只能想其他的思路来比较。

想到树可以有前中后层序遍历，如果把一棵树拍扁了，再比较，会不会就能比较出来了呢？

先复习一下二叉树的遍历。在这篇博客里已经讲得很好了：二叉树的递归和非递归方式的三种遍历。

最简单的思路是使用前序遍历，在遍历的时候，树节点在出栈的时候需要依次把右子节点和左子节点添加到栈里，如果在比较一棵树左边右边的时候，把左右子节点的进栈顺序调换，那么你就可以得到两棵镜像的树了。

按照这个思路完成的程序如下（Java 里的 Integer 类型可以用 null 简直救了一命）：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root==null || root.left==null && root.right==null) return true;
        else if(root.left==null || root.right==null) return false;
        Queue<Integer> traverse=new LinkedList<>();
        Stack<TreeNode> nodeStack=new Stack<>();

        nodeStack.push(root.left);
        while(!nodeStack.empty()){
            TreeNode t=nodeStack.pop();
            traverse.offer(t==null?null:t.val);
            if(t!=null && (t.left!=null || t.right!=null)){
                nodeStack.push(t.right);
                nodeStack.push(t.left);
            }
        }
        nodeStack.push(root.right);
        while(!nodeStack.empty()){
            TreeNode t=nodeStack.pop();
            Integer poll=traverse.poll();
            if((poll!=null && t==null) || (poll==null && t!=null) || (t!=null && poll!=t.val)) return false;
            if(t!=null && (t.left!=null || t.right!=null)){
                nodeStack.push(t.left);
                nodeStack.push(t.right);
            }
        }
        return true;
    }
}

看了一下 Solution，看见他们的代码好短啊，真香。

第一个方法是用递归来判断两个树是不是对称，真的就非常简单。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isMirror(TreeNode n1,TreeNode n2){
        if(n1==null && n2==null) return true;
        if(n1==null || n2==null) return false;
        if(n1.val==n2.val && isMirror(n1.left,n2.right) && isMirror(n1.right,n2.left)) return true;
        return false;
    }
    public boolean isSymmetric(TreeNode root) {
        return isMirror(root,root);
    }
}

他的第二个方法是把我前面两次遍历合成了一次，边入栈边判断，还省下一个 queue。（我怎么就没想到呢！）

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSymmetric(TreeNode root) {
        Queue<TreeNode> traverse=new LinkedList<>();
        traverse.offer(root);
        traverse.offer(root);
        while(!traverse.isEmpty()){
            TreeNode t1=traverse.poll();
            TreeNode t2=traverse.poll();
            if(t1==null && t2==null) continue;
            if(t1==null || t2==null) return false;
            if(t1.val!=t2.val) return false;
            traverse.add(t1.left);
            traverse.add(t2.right);
            traverse.add(t1.right);
            traverse.add(t2.left);
        }
        return true;
    }
}