显示标签为“Binary Tree”的博文。显示所有博文
显示标签为“Binary Tree”的博文。显示所有博文

2015年10月26日星期一

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 every node never differ by more than 1.
Have you met this question in a real interview? 
Yes

Example
Given binary tree A={3,9,20,#,#,15,7}, B={3,#,20,15,7}
A)  3            B)    3 
   / \                  \
  9  20                 20
    /  \                / \
   15   7              15  7
The binary tree A is a height-balanced binary tree, but B is not.

postorder the BST, get the max depth of left and right side and return the value;
if not height-balanced, return -1

Time: O(n)
Space: O(logn)

 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
29
30
31
32
/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */
class Solution {
public:
    /**
     * @param root: The root of binary tree.
     * @return: True if this Binary tree is Balanced, or false.
     */
    bool isBalanced(TreeNode *root) {
        // write your code here
        if(helper(root) == -1) return false;
        return true;
    }
    int helper(TreeNode *node){
        if(node == NULL) return 0;
        int left = helper(node->left);
        int right = helper(node->right);
        if(left == -1 || right == -1) return -1;
        if(abs(left - right) > 1) return -1;
        return max(left, right) + 1;
    }
};

发帖者 时间： 没有评论:
标签：

Converted Sorted Array to Binary Search Tree


Given an array where elements are sorted in ascending order, convert it to a height balanced BST.
http://blog.csdn.net/linhuanmars/article/details/23904883

Time: O(n)
Space: O(n)+O(logn)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * 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:
    TreeNode* sortedArrayToBST(vector<int>& nums) { 
        return helper(nums, 0, nums.size() - 1);
    }
    TreeNode* helper(vector<int>& nums, int left, int right){
        if(left > right) return NULL;
        int mid = (left + right) / 2;
        TreeNode* root = new TreeNode(nums[mid]);
        root->left = helper(nums, left, mid - 1);
        root->right = helper(nums, mid + 1, right);
        return root;
    }
};
发帖者 时间： 没有评论:
标签：

2015年9月10日星期四

Lintcode: Binary Tree Serialization

Design an algorithm and write code to serialize and deserialize a binary tree. Writing the tree to a file is called 'serialization' and reading back from the file to reconstruct the exact same binary tree is 'deserialization'.
There is no limit of how you deserialize or serialize a binary tree, you only need to make sure you can serialize a binary tree to a string and deserialize this string to the original structure.
Have you met this question in a real interview? 
Yes
Example
An example of testdata: Binary tree {3,9,20,#,#,15,7}, denote the following structure:
  3
 / \
9  20
  /  \
 15   7
Our data serialization use bfs traversal. This is just for when you got wrong answer and want to debug the input.
You can use other method to do serializaiton and deserialization.
Tags Expand 
Binary Tree

Reference:
How to use istringstream  // space will automatically separate different parameters
Note: Line 21 to_string() is necessray, string cannot add int directly
use istringstream as input, when reading values, we don't need to consider space


 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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */
 
class Solution {
private:
    void _serialize(TreeNode *root, string& out){
        if(root == NULL) {
            out += "# ";
            return;
        }
        out += to_string(root->val);
        out += " ";
        _serialize(root->left, out);
        _serialize(root->right, out);
    }
    TreeNode* _deserialize(istringstream &in){
        char str[20];
        in >> str;
        if (str[0] == '#') return NULL;
        
        TreeNode *root = new TreeNode(atoi(str));
        root->left = _deserialize(in);
        root->right = _deserialize(in);
        return root;
    }
public:
   
    string serialize(TreeNode *root) {
        // write your code here
        string res;
        _serialize(root, res);
        return res;
    }

    TreeNode *deserialize(string data) {
        // write your code here
        istringstream in(data);
        return _deserialize(in);
    }
};


Lintcode second;
BFS http://www.cnblogs.com/EdwardLiu/p/4391418.html


Total original:
represent the tree by level, all NULL represent by #
Time O(n)
Space 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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */
class Solution {
public:
    /**
     * This method will be invoked first, you should design your own algorithm 
     * to serialize a binary tree which denote by a root node to a string which
     * can be easily deserialized by your own "deserialize" method later.
     */
    string serialize(TreeNode *root) {
        // write your code here
        string res;
        queue<TreeNode *> q;
        q.push(root);
        while(!q.empty()){
            TreeNode *cur = q.front();
            q.pop();
            if(cur == NULL){
                res += ("# ");
                continue;
            }
            res += to_string(cur->val);
            res += " ",
            q.push(cur->left);
            q.push(cur->right);
        }
        return res;
    }

    /**
     * This method will be invoked second, the argument data is what exactly
     * you serialized at method "serialize", that means the data is not given by
     * system, it's given by your own serialize method. So the format of data is
     * designed by yourself, and deserialize it here as you serialize it in 
     * "serialize" method.
     */
    TreeNode *deserialize(string data) {
        // write your code here
        istringstream in(data);
        char str[20];
        queue<TreeNode *> q;
        in>>str;
        if(str[0] == '#') return NULL;
        TreeNode *head = new TreeNode(atoi(str));
        q.push(head);
        while(!q.empty()){
            TreeNode *cur = q.front();
            q.pop();
            in>>str;
            if(str[0] == '#') cur->left = NULL;
            else {
                cur->left = new TreeNode(atoi(str));
                q.push(cur->left);
            }
            in>>str;
            if(str[0] == '#') cur->right = NULL;
            else{
                cur->right = new TreeNode(atoi(str));
                q.push(cur->right);
            }
        }
        return head;
    }
};
发帖者 时间： 没有评论:
标签：

Lintcode: Validate Binary Search Tree

Given a binary tree, determine if it is a valid binary search tree (BST).
Assume a BST is defined as follows:
  • The left subtree of a node contains only nodes with keys less than the node's key.
  • The right subtree of a node contains only nodes with keys greater than the node's key.
  • Both the left and right subtrees must also be binary search trees.
Have you met this question in a real interview? 
Yes
Example
An example:
  2
 / \
1   3
   /
  4
   \
    5
The above binary tree is serialized as {2,1,3,#,#,4,#,#,5} (in level order).
Tags Expand 
Divide and Conquer Recursion Binary Search Tree Binary Tree


Two types:
1. get the max and min range of each node, traverse inorder recursively
2. traverse inorder recursively or iteratively, compare current node value and the previous traversed node value



O(n*n) naive solution:
Note: when compare left/right value with current node value, don't forget add equation ==> false
 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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */
class Solution {
public:
    /**
     * @param root: The root of binary tree.
     * @return: True if the binary tree is BST, or false
     */
    bool isValidBST(TreeNode *root) {
        // write your code here
        if(root == NULL) return true;
        int left = root->val;
        int right = root->val;
        if(root->left) {
            left = getMax(root->left);
            if (left >= root->val || !isValidBST(root->left)) return false;
        }
        if(root->right) {
            right = getMin(root->right);
            if (right <= root->val || !isValidBST(root->right)) return false;
        }
        return true;
    }
    
    int getMax(TreeNode *node){
        int res = node->val;
        int left, right;
        left = right =res;
        if(node->left) left= getMax(node->left);
        if(node->right) right = getMax(node->right);
        int big = max(left, right);
        if(big > res) return big;
        return res;
    }
    
    int getMin(TreeNode *node){
        int res = node->val;
        int left, right;
        left = right =res;
        if(node->left) left= getMin(node->left);
        if(node->right) right = getMin(node->right);
        int small = min(left, right);
        if(small < res) return small;
        return res;
    }
};

http://scyforce.gitbooks.io/leetcode/content/validate_binary_search_tree.html
Recursive: 
preorder
This is the most popular version 
Remember to make sure the range of value in node, here to pass the test, we use long type

When traverse the BST preorder, we just need root value to make sure the upper limit and bottom limit for left and right subtree. So we can transmit these two limits to next node.

Time: O(n)
Space: O(L)


 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 of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */
class Solution {
public:
   
    bool inorder(TreeNode* node, long max, long min){
        if(!node) return true;
        if(node->val >= max || node->val <= min) return false;
        return inorder(node->left, node->val, min) && inorder(node->right, max, node->val);
    }
    bool isValidBST(TreeNode *root) {
        if(!root) return true;
        return inorder(root, LONG_MAX, LONG_MIN);
    }

};
Inorder:
Global variable is needed, not recommended.
But iteritive solution avoid this problem well.
http://www.lifeincode.net/programming/leetcode-validate-binary-search-tree-java/

 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
29
30
31
32
33
/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */
class Solution {
public:
    /**
     * @param root: The root of binary tree.
     * @return: True if the binary tree is BST, or false
     */
    bool isValidBST(TreeNode *root) {
       return inorder(root);
    }
    TreeNode* prev = NULL;
    bool inorder(TreeNode* root){
        if(root == NULL) return true;
        if(!inorder(root->left)) return false;
        if(prev != NULL){
            if(root->val <= prev->val) return false;
        }
        prev = root;
        if(!inorder(root->right)) return false;
        return true;
    }
};

 Lintcode second:


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    /**
     * @param root: The root of binary tree.
     * @return: True if the binary tree is BST, or false
     */
     TreeNode *prev = NULL;
    bool isValidBST(TreeNode *root) {
        // write your code here
        if(root == NULL) return true;
        bool left = isValidBST(root->left);
        if(prev) {
            if(root->val <= prev->val) return false;
        }
        prev = root;
        bool right = isValidBST(root->right);
        return left&&right;
    }
};

Iterative:
Traverse inorder with stack, just make sure the current value is bigger than previous value
http://pengweilan.gitbooks.io/leetcode/content/Tree/validate_binary_search_tree.html
Iterative inorder BST:
 http://articles.leetcode.com/2010/04/binary-search-tree-in-order-traversal.html



 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
29
30
31
32
33
34
35
36
37
38
/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */
class Solution {
public:
    /**
     * @param root: The root of binary tree.
     * @return: True if the binary tree is BST, or false
     */
    bool isValidBST(TreeNode *root) {
        // write your code her
        stack<TreeNode*> s;
        TreeNode* cur = root;
        TreeNode* prev = NULL;
        while(!s.empty() || cur != NULL){
            if(cur != NULL){
                s.push(cur);
                cur = cur->left;
            }else{
                cur = s.top();
                s.pop();
                if(prev && prev->val >= cur->val) return false;
                prev = cur;
                cur = cur->right;
            }
        }
        return true;
    }
};




发帖者 时间： 没有评论:
标签：

Lintcode: Remove Node in Binary Search Tree

Given a root of Binary Search Tree with unique value for each node.  Remove the node with given value. If there is no such a node with given value in the binary search tree, do nothing. You should keep the tree still a binary search tree after removal.
Have you met this question in a real interview? 
Yes
Example
Given binary search tree:
          5
       /    \
    3          6
 /    \
2       4
Remove 3, you can either return:
          5
       /    \
    2          6
      \
         4
or :
          5
       /    \
    4          6
 /   
2
Tags Expand 
LintCode Copyright Binary Search Tree




There are 3 cases when deleting a node:
1. the node is leaf node
2. the node has one child
3. the node has two children: in this code, we copy the minimum number of the right subtree or the max number of the left subtree, and then delete the duplicated node in corresponding subtree, if the duplicated node still has two children, repeat the above process recursively

 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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */
class Solution {
public:
    /**
     * @param root: The root of the binary search tree.
     * @param value: Remove the node with given value.
     * @return: The root of the binary search tree after removal.
     */
    TreeNode* removeNode(TreeNode* root, int value) {
        // find the delete node 
        if(root == NULL) return NULL;
        if(root->val < value) root->right = removeNode(root->right, value);
        else if(root->val > value) root->left = removeNode(root->left, value);
        //got the node
        else{
            //0 child
            if(root->left == NULL && root->right == NULL){
                delete root;
                root = NULL;
            }
            //1 child
            else if(root->left == NULL){
                TreeNode* temp = root;
                root = root->right;
                delete temp;
            }
            else if(root->right == NULL){
                TreeNode* temp = root;
                root = root->left;
                delete temp;
            }
            //2 children
            else{
                int min = getMin(root->right);
                root->val = min;
                root->right = removeNode(root->right, min);
            }
        }
        return root;
    }
    int getMin(TreeNode* node){
        if(node->left) return getMin(node->left);
        else return node->val;
    }
};

Lintcode second:
Try reference pointer and succeed!
delete recursively without return value
find --- log(n)
delete -- O(1)

 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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */
class Solution {
public:
    /**
     * @param root: The root of the binary search tree.
     * @param value: Remove the node with given value.
     * @return: The root of the binary search tree after removal.
     */
    TreeNode *removeNode(TreeNode* &root, int value){
        _removeNode(root, value);
        return root;
    }
    void _removeNode(TreeNode* &root, int value) {
        // write your code here
        if(root == NULL) return;
        if(value > root->val) removeNode(root->right, value);
        else if(value < root->val) removeNode(root->left, value);
        else if(value == root->val){
            if(root->left == NULL && root->right == NULL){
                delete root;
                root = NULL;
            }
            else if(root->left == NULL){
                TreeNode* temp = root->right;
                delete root;
                root = temp;
            }
            else if(root->right == NULL){
                TreeNode* temp = root->left;
                delete root;
                root = temp;
            }
            else{
                root->val = getMax(root->left);
                removeNode(root->left, root->val);
            }
        }
    }
    int getMax(TreeNode* root){
        if(root->right) getMax(root->right);
        else return root->val;
    }
};
发帖者 时间： 没有评论:
标签：

Lintcode: Construct Binary Tree from Preorder and Inorder Traversal

Given preorder and inorder traversal of a tree, construct the binary tree.
Have you met this question in a real interview? 
Yes
Example
Given in-order [1,2,3] and pre-order [2,1,3], return a tree:
  2
 / \
1   3
Note
You may assume that duplicates do not exist in the tree.
Tags Expand 
Binary Tree

thoughts:
http://fisherlei.blogspot.com/2013/01/leetcode-construct-binary-tree-from.html
codes:
http://siddontang.gitbooks.io/leetcode-solution/content/tree/construct_binary_tree.html
clear codes:
http://bangbingsyb.blogspot.com/2014/11/leetcode-construct-binary-tree-from_11.html

The key is to look for root and create tree recursively
Note the margin condition!!
 http://scyforce.gitbooks.io/leetcode/content/construct_binary_tree_from_preorder_and_inorder_traversal.html (see the margin condition)

Line 32 - 37 are for loop to look for element in array which can be replaced by a hashmap

 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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */
 

class Solution {
    /**
     *@param preorder : A list of integers that preorder traversal of a tree
     *@param inorder : A list of integers that inorder traversal of a tree
     *@return : Root of a tree
     */
public:
    TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
        // write your code here
        int n = inorder.size();
        return buildTree(preorder, inorder, 0, n - 1, 0, n - 1);
    }
    
    TreeNode* buildTree(vector<int> &preorder, vector<int> &inorder, int s1, int e1, int s2,  int e2){
        if(e1 < s1 || e2 < s2) return NULL;
        TreeNode *root = new TreeNode(preorder[s1]);
        int rootIndex = -1;
        for(int i = s2; i <= e2; i++){
            if(inorder[i] == root->val) {
                rootIndex = i;
                break;
            }
        }
        //if(rootIndex == -1) return NULL;
        int leftTreeSize = rootIndex - s2;
        int rightTreeSize = e2 - rootIndex;
        root->left = buildTree(preorder, inorder, s1 + 1, s1 + leftTreeSize, s2, s2 + leftTreeSize - 1);
        root->right = buildTree(preorder, inorder, s1 + 1 + leftTreeSize, e1, rootIndex + 1, e2);
        return root;
    }
};
发帖者 时间： 没有评论:
标签：

2015年9月1日星期二

Lintcode: Convert Sorted List to Binary Search Tree

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
Have you met this question in a real interview? 
Yes
Example
               2
1->2->3  =>   / \
             1   3
Tags Expand 
Recursion Linked List

Solution:
In general, we use top to bottom way to create binary search tree. 
However, in this problem, the input is linked list, we need O(n) to look for each node, not a good one.
Another way to create binary search tree is to create from the bottom to top, kind of hard to understand, but efficient for linked list.
Create the binary search tree recursively. The key is to reference the head pointer as input parameter.
1. construct the left tree
2. construct the root, head pointer + 1
3. construct the right tree
4. return root
Time: O(n)
Stack Space:O(logn)
p.s. The best way to understand this algorithm is to run it by hands, e,g, use 0 --> 1 --> 2 --> 3 --> 4
Reference:
 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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/**
 * Definition of ListNode
 * class ListNode {
 * public:
 *     int val;
 *     ListNode *next;
 *     ListNode(int val) {
 *         this->val = val;
 *         this->next = NULL;
 *     }
 * }
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */
class Solution {
public:
    /**
     * @param head: The first node of linked list.
     * @return: a tree node
     */
    TreeNode *sortedListToBST(ListNode *head) {
        int len = 0;
        ListNode *cur = head;
        while(cur){
            len++;
            cur = cur->next;
        }
        return sortedListToBST(head, 0, len - 1);
    }
    TreeNode* sortedListToBST(ListNode* &head, int start, int end){
        if(start > end) return NULL;
        int mid = start + (end - start) / 2;
        TreeNode* left = sortedListToBST(head, start, mid - 1);
        TreeNode* root = new TreeNode(head->val);
        head = head->next;
        TreeNode* right = sortedListToBST(head, mid + 1, end);
        root->left = left;
        root->right = right;
        return root;
    }
};


发帖者 时间： 没有评论:
标签：
订阅： 博文 (Atom)