二叉树 2016-08-22

[zhaokuohaha]

100. Same Tree 110. Balanced Binary Tree +周五的题

[SnackMen]

/*
*[AC]100. Same Tree
*/
/**
 * 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 isSameTree(TreeNode p, TreeNode q) {
        if(p==null && q==null)
            return true;
        if(p==null || q==null)
            return false;
        if(q.val!=p.val)
            return false;
        boolean isTrueLeft = isSameTree(p.left,q.left);
        boolean isTrueRight = isSameTree(p.right,q.right);
        if(isTrueLeft&&isTrueRight)
            return true;
        else
            return false;
    }
}

[SnackMen]

/*
*[AC]110. Balanced Binary Tree
*/
/**
 * 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 isBalanced(TreeNode root) {
        if(root==null)
            return true;
        int leftDeep=treesDeep(root.left);
        int rightDeep = treesDeep(root.right);
        int deep = leftDeep-rightDeep;
        if(deep>1 || deep<-1)
            return false;
        return isBalanced(root.left)&&isBalanced(root.right);

    }

    public int treesDeep(TreeNode root){
        if(root==null)
            return 0;
        int leftDeep = treesDeep(root.left);
        int rightDeep = treesDeep(root.right);
        return (leftDeep>rightDeep) ? (leftDeep+1):(rightDeep+1);
    }
}

[wolfogre]

/**
 * [AC] 100. Same Tree
 * 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 isSameTree(TreeNode p, TreeNode q) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(p);
        queue.add(q);

        while(!queue.isEmpty()){
            p = queue.poll();
            q = queue.poll();

            if(p != null && q != null){
                if(p.val != q.val)
                    return false;
                queue.add(p.left);
                queue.add(q.left);
                queue.add(p.right);
                queue.add(q.right);
            } else
                if(p != q)
                    return false;
        }
        return true;
    }
}

[wolfogre]

/**
 * [AC] 110. Balanced Binary Tree
 * 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 isBalanced(TreeNode root) {
        return isBalancedHelp(root, new int[1]);
    }

    private boolean isBalancedHelp(TreeNode root, int[] maxHeight){
        if(root == null)
            return true;
        maxHeight[0] = 0;
        int[] maxLeftHeight = new int[1];
        int[] maxRightHeight = new int[1];
        if(!isBalancedHelp(root.left, maxLeftHeight))
            return false;
        if(!isBalancedHelp(root.right, maxRightHeight))
            return false;
        maxHeight[0] = Math.max(maxLeftHeight[0], maxRightHeight[0]) + 1;
        return Math.abs(maxLeftHeight[0] - maxRightHeight[0]) <= 1;
    }
}

[dayang]

/**
 * [AC] LeetCode 100 Same Tree
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {boolean}
 */
var isSameTree = function(p, q) {
    if(p === null && q === null){
        return true;
    }else if(p === null || q === null){
        return false;
    }

    if(!isSameTree(p.left,q.left)) return false;
    if(p.val !== q.val) return false;
    if(!isSameTree(p.right,q.right)) return false;

    return true;
};

[zhaokuohaha]

100 - C# - 递归

public class Solution
{
    public bool IsSameTree(TreeNode p, TreeNode q)
    {
        if (p == null && q == null) return true;
        if (p==null || q== null || p.val != q.val) return false;
        return IsSameTree(p.left, q.left) && IsSameTree(p.right, q.right);
    }
}

[zhaokuohaha]

110 - C# - 先初始化后遍历判断(总感觉可以一步到位)

public class Solution
{
    public bool IsBalanced(TreeNode root)
    {
        if(root==null) return true;
        init(root);
        return judge(root);
    }
    private bool judge(TreeNode root)
    {
        if (root.left == null || root.right == null)
            return root.val <= 1;
        if (Math.Abs(root.left.val - root.right.val) > 1)
            return false;
        return judge(root.left) && judge(root.right);
    }
    private int init(TreeNode root)
    {
        if (root == null) return -1;
        root.val = Math.Max(init(root.left), init(root.right))+1;
        return root.val;
    }
}

[dayang]

/**
 * [AC] LeetCode 110  Balanced Binary Tree
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isBalanced = function(root) {
    var flag = true;

    function depth(rt){
        if(rt === null) return 0;

        var ld = depth(rt.left);
        var rd = depth(rt.right);
        if(!flag){
            return;
        }

        if(Math.abs(ld - rd) > 1){
            flag = false;
            return;
        }

        return (Math.max(ld,rd) + 1);
    }

    depth(root);
    return flag;
};