Symmetric Tree, Leetcode 解题笔记

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.

这道题的递归解法其实并不容易想清楚,这道题值得学习:

其中左子树和右子树对称的条件:
两个节点值相等,或者都为空
左节点的左子树和右节点的右子树对称
左节点的右子树和右节点的左子树对称

/**
 * 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) {
        if(root == null) return true;
        return helper(root.left, root.right);
    }
    public boolean helper(TreeNode left, TreeNode right){
        if(left == null) return right == null;
        if(right == null) return left == null;
        if(left.val != right.val) return false;
        return helper(left.left, right.right) && helper(left.right, right.left);
    }
}

迭代解法第一反应就是层遍历(BFS),看每层的元素是否对称,注意null节点的处理,比较繁琐。

/**
 * 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) {
        LinkedList<TreeNode> q = new LinkedList<TreeNode>();
        if(root == null) return true;
        q.add(root);
        int curLevel = 1;
        int i = 0;
        while(q.size() != 0){
            while(i < curLevel){
                TreeNode temp = q.poll();
                if(temp != null){
                    q.add(temp.left);
                    q.add(temp.right);
                }
                i++;
            }
            
            int start = 0, end = q.size()-1;
            while(start < end){
                if(q.get(start) == null && q.get(end) != null) return false;
                if(q.get(end) == null && q.get(start) != null) return false;
                if(q.get(start) == null && q.get(end) == null){
                    start++;
                    end--;
                    continue;
                }
                if(q.get(start).val != q.get(end).val){
                    return false;
                }
                else{
                    start++;
                    end--;
                }
            }
            curLevel = q.size();
            i = 0;
        }
        return true;
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s