Symmetric Tree

Symmetric Tree

 

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.


Naive Way: 要求用recursive和iterative两种方法。iterative的方法可以是分别对左右子树进行DFS，一个先enqueue左节点，一个先enqueue右节点，不相等则返回。recursive的方法，因为根的两边为镜像时，左右子节点做根的时候其子树并不镜像，有点不好写。我想到了用preorder traversal和postorder traversal分别遍历得到list,比较是否一致。后来发现这两者并不是镜像（这两者肯定不是镜像的啊），于是改成比较 左-右-中  和  右-左-中 的遍历，看得到的序列是否一致。

这是我写的iterative的做法，算法复杂度O(n), space O(n)。

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean isSymmetric(TreeNode root) {
        Stack<TreeNode> left = new Stack<TreeNode>();
        Stack<TreeNode> right = new Stack<TreeNode>();
        if(root==null){return true;}
        if(root.left!=null)
            left.push(root.left);
        if(root.right!=null)
            right.push(root.right);
        while(!left.isEmpty() && !right.isEmpty()){
            TreeNode leftNode = left.pop();
            TreeNode rightNode = right.pop();
            // mirror push
            if(leftNode.val!=rightNode.val){return false;}
            if(leftNode.left!=null && rightNode.right!=null){
                left.push(leftNode.left);
                right.push(rightNode.right);
            }else{
                if(!(leftNode.left==null && rightNode.right==null))
                    return false;
            }
            if(leftNode.right!=null && rightNode.left!=null){
                left.push(leftNode.right);
                right.push(rightNode.left);
            }else{
                if(!(leftNode.right==null && rightNode.left==null))
                    return false;
            }
        }
        return left.size()==right.size();
    }
}

这是我写的recursive的做法，算法复杂度O(n), space O(n)。 当左子结点或者右子节点为空时，也必须加入list中，否则会因为轮空位置不同，不镜像的树得到相同结果。

public class Solution {
    public boolean isSymmetric(TreeNode root) {
        List<TreeNode> preorder = new ArrayList<TreeNode>();
        List<TreeNode> postorder = new ArrayList<TreeNode>();
        traversal_preorder(root, preorder);
        traversal_postorder(root, postorder);
        for(int i = 0;i < preorder.size() && i < postorder.size();i++){
            if(preorder.get(i)==null && postorder.get(i)==null)
                continue;
            if(preorder.get(i)==null || postorder.get(i)==null)
                return false;
            if(preorder.get(i).val!=postorder.get(i).val)
                return false;
        }
        return preorder.size()==postorder.size();
    }
    
    private void traversal_preorder(TreeNode root, List<TreeNode> list){
        if(root==null){return;}
        if(root.left==null)
            list.add(null);
        else
            traversal_preorder(root.left,list);
        
        if(root.right==null)
            list.add(null);
        else
            traversal_preorder(root.right,list);
        list.add(root);
    }
    
    private void traversal_postorder(TreeNode root, List<TreeNode> list){
        if(root==null){return;}
        if(root.right==null)
            list.add(null);
        else
            traversal_postorder(root.right,list);
        
        if(root.left==null)
            list.add(null);
        else
            traversal_postorder(root.left,list);
        list.add(root);
    }
}

Improved Way:显然我的这个recursive不是一个好的recursive，它实际上是一种作弊，因为不能仅通过recursive得到boolean值。后来看到了别人传递两个参数的recursive函数，茅塞顿开。

这个方法具有一般recursive的特点，就是简短，算法复杂度是O(n), space O(n)。

public class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root==null){return true;}
        return isSymmetric(root.left, root.right);
    }
    
    private boolean isSymmetric(TreeNode a, TreeNode b){
        if(a==null&&b==null){return true;}
        if(a==null||b==null){return false;}
        if(a.val!=b.val){return false;}
        return isSymmetric(a.left,b.right)&&isSymmetric(a.right,b.left);
    }
}