leetcode101.Symmetric Tree

发表于 更新于 分类于 ，

题目要求

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.

检查一棵树是否是左右对称的。

递归

在这里递归的一般情况是，输入进行比较的左子树和右子树的根节点，先判断该俩根节点是否等价，然后判断子节点是否等价。

1
2
3
4
5
6
7
8
9
10
11
12
public boolean isSymmetric(TreeNode treeNode){
    if(treeNode==null) return true;
    return isSymmetric(treeNode.left, treeNode.right);
}

public boolean isSymmetric(TreeNode left, TreeNode right){
    if(left==null && right==null) return true;
    if(left!=null && right!=null && left.val==right.val){
        return isSymmetric(left.left, right.right)&&isSymmetric(left.right, right.left);
    }
    return false;
}

栈

通过栈的形式同样可以实现比较。将需要进行比较的节点依次压入栈中。每次从栈中取出两个进行比较的节点比较。有点像level traversal的思路。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public boolean isSymmetric2(TreeNode treeNode){
    if(treeNode==null) return true;
    LinkedList<TreeNode> stack = new LinkedList<TreeNode>();
    TreeNode left = treeNode.left, right = treeNode.right;
    stack.push(left);
    stack.push(right);
    while(!stack.isEmpty()){
        right = stack.pop();
        left = stack.pop();
        if(right==null && left==null)continue;
        else if(left==null || right==null)return false;
        else if(left.val==right.val){
            stack.push(left.left);
            stack.push(right.right);
            stack.push(left.right);
            stack.push(right.left);
        }else{
            return false;
        }
    }
    return true;
}