SymmetricTree [source code]

public class SymmetricTree {
static
/******************************************************************************/
public class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) return true;
        return isMirror(root.left, root.right);
    }

    private boolean isMirror(TreeNode r1, TreeNode r2) {
        if (r1 == null && r2 == null) return true;
        else if (r1 == null || r2 == null) return false;
        else return r1.val == r2.val && isMirror(r1.left, r2.right) && isMirror(r1.right, r2.left);
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        SymmetricTree.Solution tester = new SymmetricTree.Solution();
    }
}

看起来还挺简单的一个题目, 不过最后做的时候还是费了一点周折. 刚开始我的 helper 判断的是 isSame, 但是很快意识到这个不对;
当然, 基本的一点, 这个题目是要判断两个 tree 之间的关系, 而不是按照题目描述的那样单纯判断一个 tree, 这个还是很好想到的;
然后自己画了几个例子, 可以看出来, 真正要判断的是两个 tree 成镜像. 不过这个逻辑怎么写? 如果tree1和 tree2成镜像, 那么tree1.left and tree2.right一定也成镜像, tree1.right and tree2.left一定也成镜像. 这个逻辑刚开始还是感觉不太把稳的, 所以只是写写看, 最后还是对的;

我自己刚开始写的时候, 认为 null 应该是返回 false, 但是根据 OJ 给出的 case 来看, 他们认为应该返回TRUE; 这个稍微改一下就行了, 其实感觉both ways都讲的通;

最后的时间是1(23), 一般性; 好像是最优解了;

editorial 里面给出了一个 BFS 解:

public boolean isSymmetric(TreeNode root) {  
    Queue<TreeNode> q = new LinkedList<>();  
    q.add(root);  
    q.add(root);  
    while (!q.isEmpty()) {  
        TreeNode t1 = q.poll();  
        TreeNode t2 = q.poll();  
        if (t1 == null && t2 == null) continue;  
        if (t1 == null || t2 == null) return false;  
        if (t1.val != t2.val) return false;  
        q.add(t1.left);  
        q.add(t2.right);  
        q.add(t1.right);  
        q.add(t2.left);  
    }  
    return true;  
}

刚开始我也是想着这个题目用 BFS 是可以写出来的, 果然可以, 而且代码还很简单; 循环都只用一层就搞定了;

另外注意他内部的逻辑的时候, 不像我使用大量的 land 逻辑, 而是使用了大量的premature exit来表示等小于&&的意思; 就类似一个 array, 要求是所有的都是正数(&&逻辑), 真正写代码的时候肯定可以做一个 buffer 然后全都&&=到一起, 但是也可以用for each element: if (!isPositive(element)) return false这样的逻辑来表示;

另外我这里判断 null 的另外一个简单的写法可以是这样:

    if(left==null || right==null)  
        return left==right;

这个看起来还是有点意思的;

这个是 discussion 上面看到的一个iterative DFS的:

public boolean isSymmetric(TreeNode root) {  
    if(root==null)  return true;  

    Stack<TreeNode> stack = new Stack<TreeNode>();  
    TreeNode left, right;  
    if(root.left!=null){  
        if(root.right==null) return false;  
        stack.push(root.left);  
        stack.push(root.right);  
    }  
    else if(root.right!=null){  
        return false;  
    }  

    while(!stack.empty()){  
        if(stack.size()%2!=0)   return false;  
        right = stack.pop();  
        left = stack.pop();  
        if(right.val!=left.val) return false;  

        if(left.left!=null){  
            if(right.right==null)   return false;  
            stack.push(left.left);  
            stack.push(right.right);  
        }  
        else if(right.right!=null){  
            return false;  
        }  

        if(left.right!=null){  
            if(right.left==null)   return false;  
            stack.push(left.right);  
            stack.push(right.left);  
        }  
        else if(right.left!=null){  
            return false;  
        }  
    }  

    return true;  
}

这个嗲吗相对来说就不是那么好想, 大概的思路是每一个 iteration, pop 出来两个, 是正好处于 mirror 对位的两个, 然后对这两个进行判断(val,以及 child 是否为 null), 设置premature exit, 然后将这两个的 child 按照镜像的方式一同 push 进去: 因为既然两个 parent 是应该被比较的对象, 那么两个 parent 的 children 也是应该被比较的对象. 反正就是保证需要站在镜像位置的两个 node 始终是处于 queue 里面类似于(2n-1, 2n) 的位置就行了, 以保证同时在一个 iteration 里面 pop 出来.

这个代码如果被问到, 其实还真不是轻易能够写出来的;

Problem Description

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
Note:
Bonus points if you could solve it both recursively and iteratively.

Difficulty:Easy
Category:Algorithms
Acceptance:38.38%
Contributor: LeetCode
Companies
linkedin bloomberg microsoft
Related Topics
tree depth-first search breadth-first search