leetcode 101.Symmetric Tree

2017-07-31

题意

对称树，判断一个树是否是对称的。

我的思想

首先避开第一个节点，对比它的左右树。采用先序遍历法遍历左树，后序遍历遍历右边的树对比

我的代码

递归实现的方法

/**
 * Definition for a binary tree node.
 * 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||(root.left==null&&root.right==null))
            return true;
        return travelTree(root.left,root.right);
    }
    public boolean travelTree(TreeNode leftroot,TreeNode rightroot){
        if(leftroot==null&&rightroot==null)
            return true;
        if(leftroot!=null&&rightroot!=null)
        {
            if(leftroot.val==rightroot.val)
                return travelTree(leftroot.left,rightroot.right)&&travelTree(leftroot.right,rightroot.left);
        }
        return false;
    }
}

大神代码

把前面第一个节点对左右树的判断融汇到了递归中！这样子会多遍历一遍root树。
学习了代码缩减的方法。一个return 直接写在if后面

public class Solution {
    public boolean isSymmetric(TreeNode root) {
        return travelTree(root,root);
    }
    public boolean travelTree(TreeNode leftroot,TreeNode rightroot){
        if(leftroot==null&&rightroot==null)return true;
        if(leftroot==null||rightroot==null) return false;
        return (leftroot.val==rightroot.val)&&travelTree(leftroot.left,rightroot.right)&&travelTree(leftroot.right,rightroot.left);
    }
}

非递归实现的方法，使用了队列。

public boolean isSymmetric(TreeNode root) {
    Queue<TreeNode> q = new LinkedList<>();
    q.add(root);
    q.add(root);
    while (!q.isEmpty()) {
        TreeNode t1 = q.poll();
        TreeNode t2 = q.poll();
        if (t1 == null && t2 == null) continue;
        if (t1 == null || t2 == null) return false;
        if (t1.val != t2.val) return false;
        q.add(t1.left);
        q.add(t2.right);
        q.add(t1.right);
        q.add(t2.left);
    }
    return true;
}

非递归实现的方法，使用了栈

public boolean isSymmetric(TreeNode root) {
    if(root==null)  return true;

    Stack<TreeNode> stack = new Stack<TreeNode>();
    TreeNode left, right;
    if(root.left!=null){
        if(root.right==null) return false;
        stack.push(root.left);
        stack.push(root.right);
    }
    else if(root.right!=null){
        return false;
    }
    while(!stack.empty()){
        if(stack.size()%2!=0)   return false;
        right = stack.pop();
        left = stack.pop();
        if(right.val!=left.val) return false;

        if(left.left!=null){
            if(right.right==null)   return false;
            stack.push(left.left);
            stack.push(right.right);
        }
        else if(right.right!=null){
            return false;
        }

        if(left.right!=null){
            if(right.left==null)   return false;
            stack.push(left.right);
            stack.push(right.left);
        }
        else if(right.left!=null){
            return false;
        }
    }

    return true;
}