[LeetCode] Path Sum, Solution

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

For example:
Given the below binary tree and sum = 22,

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \      \
        7    2      1

return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

» Solve this problem

[Thoughts]
二叉树遍历。遍历过程中累加节点值，当到达任意叶节点的时候，进行判断。


[Code]

1:       bool hasPathSum(TreeNode *root, int sum) {  
2:            return hasPathSum(root, 0, sum);      
3:       }  
4:       bool hasPathSum(TreeNode *root, int sum, int target) {  
5:            if(root == NULL) return false;  
6:            sum += root->val;  
7:            if(root->left == NULL && root->right == NULL) //leaf  
8:            {  
9:                 if(sum == target)  
10:                      return true;  
11:                 else  
12:                      return false;  
13:            }  
14:            return hasPathSum(root->left, sum, target)   
15:                   || hasPathSum(root->right, sum, target);      
16:       }  

[Interview] Serialize and De-serialize a tree

A very frequent interview question. Suppose you have a tree, how could you serialize it to file and revert it back?


for example,

                                               1
                                         /               \
                                        2                 3
                                             \          /    
                                             4        5    
                                          /       \
                                         6        7

[Thoughts]
一个比较简单直接的做法是，通过前序遍历来做，把所有空节点当做“#”来标示。那么这棵树可以表示为

                                               1
                                         /               \
                                        2                 3
                                     /       \          /      \
                                  #         4        5       #
                                          /       \
                                         6        7
                                     /      \     /    \
                                    #      #    #     #

那么前序遍历的结果就是： {'1','2','#','4','6','#','#','7','#','#','3','5','#','#','#'}; 代码如下：

void Serialize(TreeNode * node, vector<char> &output)

{

       if(node == NULL)

       {

             output.push_back('#');

             return;

       }

       output.push_back(node->val + '0');

       Serialize(node->left, output);

       Serialize(node->right, output);

}

而反序列化的代码也就是：

TreeNode *Deserialize(vector<char> output, int &index)

{

       if(index > output.size() || output[index] == '#') return NULL;

       TreeNode *node = new TreeNode(output[index] -'0');

       index ++;

       node->left = Deserialize(output, index);

       index++;

       node->right = Deserialize(output, index);

       return node;

}

这里只能通过前序遍历来做，中序及后序是行不通的。原因很简单，除了前序以外，其他遍历方式没办法找出头结点。

除了常规的三种遍历方式意外， 另一种可行的方法就是按层来遍历，同样可行。

[LeetCode] Convert Sorted Array to Binary Search Tree, Solution

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

» Solve this problem

[Thoughts]
If we build BST from array, we can build it from top to bottom, like
1. choose the middle one as root,
2. build left sub BST via left part array
3. build right sub BST via right part array
4. do this recursively.


[Code]

1:       TreeNode *sortedArrayToBST(vector<int> &num) {  
2:            return BuildTree(num, 0, num.size()-1);  
3:       }  
4:       TreeNode *BuildTree(vector<int> &num, int start, int end)  
5:       {  
6:            if(start>end) return NULL;  
7:            if(start == end) return new TreeNode(num[start]);  
8:            int mid = (start+end)/2;  
9:            TreeNode *node = new TreeNode(num[mid]);  
10:           node->left = BuildTree(num, start, mid-1);  
11:           node->right = BuildTree(num, mid+1, end);  
12:           return node;  
13:       }  

[LeetCode] Same Tree, Solution

Given two binary trees, write a function to check if they are equal or not.

Two binary trees are considered equal if they are structurally identical and the nodes have the same value.

» Solve this problem


[Thoughts]
递归判断左右子树是否相等。


[Code]

1:    bool isSameTree(TreeNode *p, TreeNode *q) {  
2:      if(!p && !q) return true;  
3:      if(!p || !q) return false;  
4:      return (p->val == q->val) &&  
5:           isSameTree(p->left, q->left) &&   
6:           isSameTree(p->right, q->right);      
7:    }  

[LeetCode] Unique Binary Search Trees II, Solution

Given n, generate all structurally unique BST's (binary search trees) that store values 1...n.

For example,
Given n = 3, your program should return all 5 unique BST's shown below.

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

» Solve this problem


[Thoughts]
分析请参看http://fisherlei.blogspot.com/2013/03/leetcode-unique-binary-search-trees.html
思路是一致的。划分左右子树，然后递归构造。

[Code]

1:       vector<TreeNode *> generateTrees(int n) {   
2:            if(n ==0) return generate(1,0);  
3:            return generate(1, n);  
4:       }       
5:       vector<TreeNode *> generate(int start, int end)  
6:       {  
7:            vector<TreeNode *> subTree;  
8:            if(start>end)  
9:            {  
10:                 subTree.push_back(NULL);  
11:                 return subTree;  
12:            }  
13:            for(int i =start; i<=end; i++)  
14:            {  
15:                 vector<TreeNode*> leftSubs = generate(start, i-1);  
16:                 vector<TreeNode*> rightSubs = generate(i+1, end);  
17:                 for(int j = 0; j< leftSubs.size(); j++)  
18:                 {  
19:                      for(int k=0; k<rightSubs.size(); k++)  
20:                      {  
21:                           TreeNode *node = new TreeNode(i);  
22:                           node->left = leftSubs[j];  
23:                           node->right = rightSubs[k];  
24:                           subTree.push_back(node);  
25:                      }  
26:                 }  
27:            }  
28:            return subTree;  
29:       }      

[Note]
写完第一个版本之后，立即发现一个严重的问题。上面的function存在大量的对象拷贝，因为所有变量都是在栈上开辟，所以返回值的时候都需要通过拷贝构造函数来重构vector，面试中这个疏忽是不应该的。

修改版，这里应该用指针及堆来存储变量。

1:       vector<TreeNode *> generateTrees(int n) {   
2:            if(n ==0) return *generate(1,0);  
3:            return *generate(1, n);  
4:       }  
5:       vector<TreeNode *>* generate(int start, int end)  
6:       {  
7:            vector<TreeNode *> *subTree = new vector<TreeNode*>();  
8:            if(start>end)  
9:            {  
10:                 subTree->push_back(NULL);  
11:                 return subTree;  
12:            }  
13:            for(int i =start; i<=end; i++)  
14:            {  
15:                 vector<TreeNode*> *leftSubs = generate(start, i-1);  
16:                 vector<TreeNode*> *rightSubs = generate(i+1, end);  
17:                 for(int j = 0; j< leftSubs->size(); j++)  
18:                 {  
19:                      for(int k=0; k<rightSubs->size(); k++)  
20:                      {  
21:                           TreeNode *node = new TreeNode(i);  
22:                           node->left = (*leftSubs)[j];  
23:                           node->right = (*rightSubs)[k];  
24:                           subTree->push_back(node);  
25:                      }  
26:                 }  
27:            }  
28:            return subTree;  
29:       }      

[LeetCode] Unique Binary Search Trees, Solution

Given n, how many structurally unique BST's (binary search trees) that store values 1...n?

For example,
Given n = 3, there are a total of 5 unique BST's.

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

» Solve this problem

[Thoughts]
这题想了好久才想清楚。其实如果把上例的顺序改一下，就可以看出规律了。
 1                1                      2                       3             3
    \                 \                 /      \                  /              /
      3               2              1       3               2             1
    /                   \                                       /                  \
 2                       3                                   1                    2

比如，以1为根的树有几个，完全取决于有二个元素的子树有几种。同理，2为根的子树取决于一个元素的子树有几个。以3为根的情况，则与1相同。

定义Count[i] 为以[0,i]能产生的Unique Binary Tree的数目，

如果数组为空，毫无疑问，只有一种BST，即空树，
Count[0] =1

如果数组仅有一个元素{1}，只有一种BST，单个节点
Count[1] = 1

如果数组有两个元素{1,2}， 那么有如下两种可能
1                       2
  \                    /
    2                1
Count[2] = Count[0] * Count[1]   (1为根的情况)
                  + Count[1] * Count[0]  (2为根的情况。

再看一遍三个元素的数组，可以发现BST的取值方式如下：
Count[3] = Count[0]*Count[2]  (1为根的情况)
               + Count[1]*Count[1]  (2为根的情况)
               + Count[2]*Count[0]  (3为根的情况)

所以，由此观察，可以得出Count的递推公式为
Count[i] = ∑ Count[0...k] * [ k+1....i]     0<=k<i-1
问题至此划归为一维动态规划。

[Code]

1:       int numTrees(int n) {  
2:            vector<int> count(n+1, 0);  
3:            count[0] =1;  
4:            count[1] =1;  
5:            for(int i =2; i<=n; i++)  
6:            {  
7:                 for(int j =0; j<i; j++)  
8:                 {  
9:                      count[i] += count[j]*count[i-j-1];   
10:                 }  
11:            }  
12:            return count[n];  
13:       }  

[Note]
这是很有意思的一个题。刚拿到这题的时候，完全不知道从那下手，因为对于BST是否Unique，很难判断。最后引入了一个条件以后，立即就清晰了，即
当数组为 1，2，3，4，.. i，.. n时，基于以下原则的BST建树具有唯一性：
以i为根节点的树，其左子树由[0, i-1]构成， 其右子树由[i+1, n]构成。

[LeetCode] Remove Duplicates from Sorted List II, Solution

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

For example,
Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.

» Solve this problem

[Thoughts]
实现题。前面加一个Safeguard，这样可以避免处理头结点的复杂。

[Code]

1:       ListNode *deleteDuplicates(ListNode *head) {  
2:            if(head == NULL) return head;  
3:            ListNode *G = new ListNode(INT_MIN);  
4:            G->next = head;  
5:            ListNode *cur = G, *pre = head;  
6:            while(pre!=NULL)  
7:            {  
8:                 bool isDup = false;  
9:                 while(pre->next!=NULL && pre->val == pre->next->val)  
10:                 {  
11:                      isDup = true;  
12:                      ListNode *temp = pre;  
13:                      pre = pre->next;  
14:                      delete temp;  
15:                 }  
16:                 if(isDup)  
17:                 {  
18:                      ListNode *temp = pre;  
19:                      pre = pre->next;  
20:                      delete temp;  
21:                      continue;  
22:                 }  
23:                 cur->next = pre;  
24:                 cur = cur->next;  
25:                 pre= pre->next;  
26:            }  
27:            cur->next = pre;  
28:            ListNode *temp = G->next;  
29:            delete G;  
30:            return temp;      
31:       }