101. Symmetric Tree

Solution

Symmetric tree，要滿足左子樹，右子樹互為境像。

成為境像的條件式，除了兩子樹的根節點相同外，其根節點底下的下層子樹也要互為境像。

T: O(N) Recursive:

    public boolean isSymmetric(TreeNode root) {
        return isMirror(root, root);
    }
    public boolean isMirror(TreeNode q, TreeNode p){
        
        if(q == null && p == null) return true;
        else if (q == null || p == null) return false;
        return q.val == p.val && isMirror(q.left, p.right) && isMirror(q.right, p.left);
    }

Iteration

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