101. Symmetric Tree.md

101. Symmetric Tree

Problem

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

For example, this binary tree is symmetric:

    1
   / \
  2   2
 / \ / \
3  4 4  3
But the following is not:
    1
   / \
  2   2
   \   \
   3    3

Note: Bonus points if you could solve it both recursively and iteratively.

tag:

Solution

递归

树中两个点对称(n1,n2)， 递归判断n1的左子树与n2的右子树，n2的右子树与n2的左子树是否对称

java

    public boolean isSymmetric(TreeNode root) {
       return root==null || helper(root.left, root.right); 
    }
    
    boolean helper(TreeNode n1, TreeNode n1) {
        if(n1==null || n2==null) return n1==n2;
        if(n1.val != n2.val) return false;
        return helper(n1.left, n2.right)&&helper(n1.right, n2.left);
    }

go

迭代

模拟递归工作栈

    public boolean isSymmetric(TreeNode root) {
       if(root==null) return true;
       
       Stack<TreeNode> s = new Stack<TreeNode>();
       
       if(root.left!=null && root.right!=null) {
           s.push(root.left);
           s.push(root.right);
       } else if(root.left==null && root.right==null) {
           return true;
       } else {
           return false;
       }
           
       TreeNode left, right;
       
       while(!s.isEmpty()) {
          // if(s.size()%2!=0) return false;
           right = s.pop();
           left = s.pop();
           if(right.val!=left.val) return false;
           
           if(left.left!=null && right.right!=null) {
               s.push(left.left);
               s.push(right.right);
           } else if(!(left.left==null&&right.right==null)) {
              return false;
           }
            
           if(left.right!=null && right.left!=null) {
               s.push(left.right);
               s.push(right.left);
           } else if(!(left.right==null && right.left==null)) {
               return false;
           }
       }
       
       return true;
    }

层次遍历，判断每层是否对称