首页 > ACM题库 > LeetCode > Symmetric Tree[LeetCode]对称二叉树
2014
11-10

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

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

提示:是否可以同时用递归和迭代的方法解决?

方法一 递归 Recursively

这里其实的对两课子树同时进行递归判断。

public class SymmetricTree {
    static class TreeNode {
           int val;
            TreeNode left;
            TreeNode right;
            TreeNode(int x) { val = x; }
        }
    public boolean isSymmetric(TreeNode root) {
        if(root == null) return true;
        return isSymmetric(root.left, root.right);
    }
    public boolean isSymmetric(TreeNode leftNode, TreeNode rightNode){
        if(leftNode == null && rightNode == null ) return true;
        if(leftNode == null || rightNode == null) return false;
        if(leftNode.val != rightNode.val) return  false;
        boolean isLeft = isSymmetric(leftNode.left, rightNode.right);
        boolean isRight = isSymmetric(leftNode.right, rightNode.left);
        return isLeft && isRight;
    }

    public static void main(String args[]){
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(2);
        root.left.left = new TreeNode(3);
        root.left.right = new TreeNode(4);
        root.right.left = new TreeNode(4);
        root.right.right = new TreeNode(3);
        System.out.println(new SymmetricTree().isSymmetric(root));
        System.out.println(new SymmetricTree().isSymmetricIter(root));
    }
}

 方法二 迭代 Iteratively

起初打算用层次遍历的方法,然后判断每一层是否是对称的,但是觉得有问题。例如对于:

    1
   / \
  2   2
 /   / 
3   3

并不是对称的,但是在遍历到最后一层,无法判断是否是对称的。

这里使用两个栈,分别对两个子树进行遍历,左子树先序遍历,右子树则反向的遍历。

public boolean isSymmetricIter(TreeNode root) {
        if(root == null) return true;
        Stack<TreeNode> leftStack = new Stack<TreeNode>();
        Stack<TreeNode> rightStack = new Stack<TreeNode>();
        leftStack.push(root.left);
        rightStack.push(root.right);

        while (leftStack.size() > 0 && rightStack.size() > 0){
            TreeNode left = leftStack.pop();
            TreeNode right = rightStack.pop();
            if(left == null && right == null) continue;
            if(left == null || right == null) return false;
            if(left.val == right.val) {
                leftStack.push(left.right);
                leftStack.push(left.left);
                rightStack.push(right.left);
                rightStack.push(right.right);
            }else{
                return false;
            }
        }
        return true;
    }

  1. L(X [0 .. M-1],Y [0 .. N-1])= 1 + L(X [0 .. M-2],Y [0 .. N-1])这个地方也也有笔误
    应改为L(X [0 .. M-1],Y [0 .. N-1])= 1 + L(X [0 .. M-2],Y [0 .. N-2])

  2. 我还有个问题想请教一下,就是感觉对于新手来说,递归理解起来有些困难,不知有没有什么好的方法或者什么好的建议?

  3. #include <cstdio>
    #include <cstring>

    const int MAXSIZE=256;
    //char store[MAXSIZE];
    char str1[MAXSIZE];
    /*
    void init(char *store) {
    int i;
    store['A']=’V', store['B']=’W',store['C']=’X',store['D']=’Y',store['E']=’Z';
    for(i=’F';i<=’Z';++i) store =i-5;
    }
    */
    int main() {
    //freopen("input.txt","r",stdin);
    //init(store);
    char *p;
    while(fgets(str1,MAXSIZE,stdin) && strcmp(str1,"STARTn")==0) {
    if(p=fgets(str1,MAXSIZE,stdin)) {
    for(;*p;++p) {
    //*p=store[*p]
    if(*p<’A’ || *p>’Z') continue;
    if(*p>’E') *p=*p-5;
    else *p=*p+21;
    }
    printf("%s",str1);
    }
    fgets(str1,MAXSIZE,stdin);
    }
    return 0;
    }