leetcode Question 7: Balanced Binary Tree

Balanced Binary Tree

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 everynode never differ by more than 1.

Analysis:

Note here is slightly different from the Cracking the Code Interview 4.1, one can notice that the code from 4.1 will not pass all the test samples here. That is because the definition of balanced. In 4.1, balanced is defined by all the node differs in depth less than or equal to 1. But here balanced is defined the difference of max depth of left tree and right tree are less than or equal to 1.

The key idea is from the 4.1, where compute the max and min depth of the whole tree and see the difference. Here, we compute the max depth of two sub tree of a node, if the difference is > 1, output false.


The source code of Cracking the Code Interview 4.1 :

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode * root){
        if (root==NULL){return 0;}
        return 1+max(maxDepth(root->left),maxDepth(root->right));
    }
    int minDepth(TreeNode * root){
        if (root==NULL){return 0;}
        return 1+min(minDepth(root->left),minDepth(root->right));
    }
    bool isBalanced(TreeNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int maxd = maxDepth(root);
        int mind = minDepth(root);
        if (abs(maxd-mind)<=1) {return true;} else {return false;}
    }
 
};

Code(C++) :

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode * root){
        if (root==NULL){return 0;}
        return 1+max(maxDepth(root->left),maxDepth(root->right));
    }
    
    bool testNode(TreeNode * root){
        if (root==NULL) {return true;}
        if (abs(maxDepth(root->left) - maxDepth(root->right)) >1) {return false;}
        return (testNode(root->left) && testNode(root->right));
    }
    
    
    bool isBalanced(TreeNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        return testNode(root);
    }
    
};

Code(Python):

# Definition for a  binary tree node
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    # @param root, a tree node
    # @return a boolean
    def maxd(self, root):
        if root == None:
            return 0
        else:
            return 1 + max(self.maxd(root.left), self.maxd(root.right))
    def testNode(self, root):
        if root == None:
            return True
        else:
            if abs(self.maxd(root.left) - self.maxd(root.right)) > 1:
                return False
            else:
                return self.testNode(root.left) and self.testNode(root.right)
    def isBalanced(self, root):
        return self.testNode(root)