2015年7月4日星期六

LeetCode: Balanced Binary Tree

First time bug free pass directly, cheers!

Divide and conquer method:
Here uses divide and conquer method for two function.
First is balance judgement.
O(n*n)  (n=number of nodes)
For each element, calculate the left and right depth. If the distance of left and right depth is more than 1, return false. If not, test the left and right element.

Second is depth calculation.
O(n)
Get the longest depth of the current node.

Initial code:
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isBalanced(TreeNode* root) {
        if(root == NULL) return true;
        int left, right;
        left = Caldeep(root->left);
        right = Caldeep(root->right);
        if(left - right >1 || right - left >1) return false;
        return isBalanced(root->left) && isBalanced(root->right);
        
    }
    int Caldeep(TreeNode* node){
        if(node == NULL) return 0;
        int left=1, right=1;
        if(node->left != NULL) left = Caldeep(node->left)+1;
        if(node->right != NULL) right = Caldeep(node->right)+1;
        return (left>right)?left:right;
    }
};

Modified in a better format:


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isBalanced(TreeNode* root) {
        if(root == NULL) return true;
        int left = Caldepth(root->left);
        int right = Caldepth(root->right);
        if(left-right >1 || right-left > 1) return false;
        return isBalanced(root->left) && isBalanced(root->right);
        
    }
    int Caldepth(TreeNode* node){
        if(node == NULL) return 0;
        int left = Caldepth(node->left)+1;
        int right = Caldepth(node->right)+1;
        return (left>right)?left:right;
    }
};



Optimization Analysis: 

 In solutions above, there are many repetitive calculation of depth. Actually,  unbalance can be recognized in caldepth() function if we use -1 to track this unbalanced state.
Time complexity here is O(n)


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isBalanced(TreeNode* root) {
        if(root == NULL) return true;
        int val=Caldepth(root);
        if(val==-1) return false;
        return true;
    }
    int Caldepth(TreeNode* node){
        if(node == NULL) return 0;
        int left = Caldepth(node->left);
        int right = Caldepth(node->right);
        if(left == -1 || right == -1) return -1;
        if(left - right >1 || right - left >1) return -1;
        return (left>right)?left+1:right+1;
    }
};


发帖者 时间：
标签： ,

没有评论:

发表评论

订阅： 博文评论 (Atom)