leetcode 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

如果想要写出简洁漂亮的递归程序,首先应该判断不符合条件的情况,再写代码就比较清晰了。
如果首先考虑符合条件的情况,代码可能就会比较复杂。


import java.util.Stack;

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 *
 *
 */


public class SymmetricTree {
/**
 * 递归实现
 * */
    public boolean isSymmetric(TreeNode root) {
        if (root == null) return true;
        if(root.left != null && root.right != null
                && root.left.val == root.right.val) {//root‘s left == root's right then recurs

            return isMirror(root.right, root.left) ;//judge
        }else if (root.left == null &&  root.right == null){
            return true;
        }else {
            return false;
        }
    }

    private boolean isMirror(TreeNode right, TreeNode left) {
        boolean isMir1 = false;
        boolean isMir2 = false;

        if (right.right != null && left.left != null && right.right.val == left.left.val){
            isMir2 = isMirror(right.right, left.left);//判断右子树右节点与左子树左节点是否是镜像
        }else if (right.right == null && left.left == null){
            isMir2 = true;
        }else {
            return false;
        }

        if (right.left !=null &&  left.right != null  && left.right.val == right.left.val){
            isMir1 = isMirror(right.left, left.right);
        }else if (right.left == null && left.right == null) {//判断左子树右节点与右子树左节点是否是镜像
            isMir1 = true;
        }else {
            return false;
        }


        return isMir1 &&  isMir2;

    }


/**
* 遍历实现,非递归
* no recursion
* */
    public boolean isSymmetric2(TreeNode root){

        TreeNode p = root;
        TreeNode pRight = root;
        TreeNode pLeft = root;
        boolean symmetricFlg  =true;

        Stack <TreeNode> sRight = new Stack<TreeNode>();
        Stack <TreeNode> sLeft = new Stack<TreeNode>();



        if (root == null) return true;
            if (root.left != null && root.right != null
                    && root.left.val == root.right.val) {//root‘s left == root's right then recurs
                sLeft.push(p.left);
                sRight.push(p.right);

                while (!sLeft.isEmpty() && !sRight.isEmpty()){
                    pRight = sRight.pop();
                    pLeft = sLeft.pop();
                    if (pRight.right!=null && pLeft.left != null
                            && pRight.right.val == pLeft.left.val ){
                        sLeft.push(pLeft.left);
                        sRight.push(pRight.right);
                    }else if (pRight.right == null && pLeft.left == null){

                    }else{
                        return false;
                    }

                    if (pRight.left!=null && pLeft.right != null
                            && pRight.left.val == pLeft.right.val ){
                        sLeft.push(pRight.left);
                        sRight.push(pLeft.right);
                    }else if (pRight.left == null && pLeft.right == null){

                    }else{
                        return false;
                    }




                }
            } else if (root.left == null && root.right == null) {
                return true;
            } else {
                return false;
            }
        return true;
    }

/**
 * beautiful neat recursion code by lanb
 * 先考虑不合理的情况,再进行递归
 * */
    public boolean isSymmetric3(TreeNode root){
        if (root == null) {
            return true;
        }

        return helper(root.left, root.right);
    }

    private boolean helper(TreeNode a, TreeNode b) {
        if (a == null && b == null) return true;
        if (a == null || b == null) return false;  // only one has node in a tree and b tree
        if (a.val != b.val) return false;
        return helper(a.left, b.right) && helper(a.right, b.left); // a goes in in-order traversal, b goes right first then left.
    }




    /**
     * 遍历,非递归实现 code by  xuanaux
     * */

    public boolean isSymmetric4(TreeNode root) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        if (root == null) return true;
        Stack<TreeNode> s1 = new Stack<TreeNode>();
        Stack<TreeNode> s2 = new Stack<TreeNode>();
        s1.push(root.left);
        s2.push(root.right);
        while (!s1.empty() && !s2.empty()) {
            TreeNode n1 = s1.pop();
            TreeNode n2 = s2.pop();
            if (n1 == null && n2 == null) continue;
            if (n1 == null || n2 == null) return false;
            if (n1.val != n2.val) return false;
            s1.push(n1.left);
            s2.push(n2.right);
            s1.push(n1.right);
            s2.push(n2.left);
        }
        return true;
    }

}

							
Tagged on: , , ,

发表评论

电子邮件地址不会被公开。 必填项已用*标注

This site uses Akismet to reduce spam. Learn how your comment data is processed.