美文网首页
110. Balanced Binary Tree

110. Balanced Binary Tree

作者: Nancyberry | 来源:发表于2018-05-18 09:23 被阅读0次

    Description

    Given a binary tree, determine if it is height-balanced.

    For this problem, a height-balanced binary tree is defined as:

    a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

    Example 1:

    Given the following tree [3,9,20,null,null,15,7]:

    tree

    Return true.

    Example 2:

    Given the following tree [1,2,2,3,3,null,null,4,4]:

    tree

    Return false.

    Solution

    DFS, time O(n), space O(h)

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        public boolean isBalanced(TreeNode root) {
            if (root == null) {
                return true;
            }
            
            return isBalanced(root.left) && isBalanced(root.right)
                && Math.abs(depth(root.left) - depth(root.right)) <= 1;
        }
        
        private int depth(TreeNode root) {
            if (root == null) {
                return 0;
            }
            
            return 1 + Math.max(depth(root.left), depth(root.right));
        }
    }
    

    相关文章

      网友评论

          本文标题:110. Balanced Binary Tree

          本文链接:https://www.haomeiwen.com/subject/cqvwdftx.html