Balanced Binary Tree

本文主要是介绍Balanced Binary Tree，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

Code link: https://leetcode.com/problems/balanced-binary-tree/

Constraint:

• The number of nodes in the tree is in the range [0, 5000]. This means we can use recursion?

Idea:

Note the definition of height and depth might be differnt from the official definition of Wikipedia. In this question, the depth is the number of nodes from root to that spesific node, but not the number of paths.

First we could get the height of a node's left and right subtree, and check if they are balanced. Then we could do this check recursively against current nodes' left and right tree. This is like a top-down way of search.

Code

1. Attempt 1

class Solution {
    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }
        
        int lh = getHeight(root.left);
        int rh = getHeight(root.right);
        if (Math.abs(lh - rh) > 1) {
            return false;
        }
        
        return isBalanced(root.left) && isBalanced(root.right);
    }
    
    private int getHeight(TreeNode root) {
        if (root == null) {
            return 0;
        }
        
        return Math.max(getHeight(root.left), getHeight(root.right)) + 1;
    }
}

• Time: O(n^2). The time for getHeight() would be O(n) as we have to traverse all nodes in the case of a skew tree. This means for each recursion call, we spend O(n). And we have to do this for all the N nodes, resulting to O(n^2).
• Space: O(n). This would be equal to the max height of a tree.

2. Attempt 2
   A better way is to solve it in bottom-up way. When checking the height of a subtree, return something invalid when the tree is unbalanced. Normally tree height would never be negative, so we could return negative number in case the current subtree is unbalanced. And if there's any unbalanced subtree, it vialotes the definiton of being balanced. We simply need to return negative number all the way up.

class Solution {
    public boolean isBalanced(TreeNode root) {
        return getHeight(root) != -1;
    }
    
    private int getHeight(TreeNode root) {
        if (root == null) {
            return 0;
        }
        
        int lh = getHeight(root.left);
        int rh = getHeight(root.right);
        if (lh == -1 || rh == -1 || Math.abs(lh - rh) > 1) {
            return -1;
        }
        
        return Math.max(lh, rh) + 1;
    }
}

• Time: O(n). The method getHeight() is O(n).

• Space: O(n).

• Similar problem:

  • https://leetcode.com/problems/maximum-depth-of-binary-tree/

这篇关于Balanced Binary Tree的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！