leetcode Ch3-DFS & Backtracking I

一、树的遍历

【非递归版】

 1 class Solution
 2 {
 3 public:
 4     vector<int> postorderTraversal(TreeNode *root)
 5     {
 6         vector<int> answer;
 7         stack<pair<TreeNode*,int>> s;
 8         s.push(make_pair(root,0));
 9         while(!s.empty())
10         {
11             TreeNode *now=s.top().first;
12             if(now==NULL)
13             {
14                 s.pop();
15             }
16             else
17             {
18                 switch(s.top().second++)
19                 {
20                     case 0:
21                         s.push(make_pair(now->left,0));
22                         break;
23                     case 1:
24                         s.push(make_pair(now->right,0));
25                         break;
26                     case 2:
27                         s.pop();
28                         answer.push_back(now->val);
29                         break;
30                 }
31             }
32         }
33         return answer;
34     }
35 };

View Code

这里用pair中的first存放指针，second存放一个int值。这个int值是用来标记当前节点的孩子（子树）的访问情况，值取0表示该节点的左孩子、右孩子都尚未访问；值取1表示左孩子已访问，右孩子尚未访问；值取2表示左右孩子都已访问过。这样，当值为2时就可以把当前结点的值输出（后序的定义）。

update1: 记得判断栈顶元素对应的first指针非空。

2.先序/前序

如果按基于上面后序的代码模式来改写，也可以轻松的改为先序。只是没有必要这么繁琐。后面有个不基于改写的、简化版的。

改写版的代码如下

 1 class Solution
 2 {//trying to change postorder to preorder
 3 public:
 4     vector<int> preorderTraversal(TreeNode *root)
 5     {
 6         vector<int> answer;
 7         stack<pair<TreeNode*,int>> s;
 8         s.push(make_pair(root,0));
 9         while(!s.empty())
10         {
11             TreeNode *now=s.top().first;
12             if(now==NULL)
13             {
14                 s.pop();
15             }
16             else
17             {
18                 if(s.top().second==0)//this can guarantee the node will not be repeatedly pushed into answer.
19                     answer.push_back(now->val);
20                 switch(s.top().second++)
21                 {
22                     case 0:
23                         s.push(make_pair(now->left,0));
24                         break;
25                     case 1:
26                         s.push(make_pair(now->right,0));
27                         break;
28                     case 2:
29                         s.pop();
30                         //answer.push_back(now->val);
31                         break;
32                 }
33             }
34         }
35         return answer;
36     }
37 };

View Code

1 这样的改写是有效的，但是其实不必这么麻烦。因为对后序来说，必须要保存一个int值记录状态信息，从而在节点的左右子树都访问过后才能输出该节点的value。但是对前序而言，实际上只要遇到节点就输出其value即可，然后把该节点左右孩子压入栈，之后该节点就没有存在价值了。因此，前序不用像后序那样用一个int来记录状态信息。
2 
3 这里需要注意的是，在将节点的左右孩子压入栈时，应该先压入其右孩子，再压入其左孩子。

Explanation

简化版代码如下：

 1 class Solution
 2 {
 3 public:
 4     vector<int> preorderTraversal(TreeNode* root)
 5     {
 6         vector<int> answer;
 7         stack<TreeNode*> s;
 8         s.push(root);
 9         while(!s.empty())
10         {
11             TreeNode* now=s.top();
12             s.pop();//don't forget!
13             if(now!=NULL)
14             {
15                 answer.push_back(now->val);
16                 s.push(now->right);
17                 s.push(now->left);
18             }
19         }
20         return answer;
21     }
22 };

View Code

update 8.9

 1 vector<int> preorderTraversal(TreeNode* root) {
 2     vector<int> result;
 3     stack<TreeNode*> s;
 4     s.push(root);
 5     while (!s.empty()) {
 6         TreeNode* cur = s.top();
 7         if (cur == NULL) {
 8             s.pop();
 9         } else {
10             result.push_back(cur->val);
11             s.pop();
12             s.push(cur->right);
13             s.push(cur->left);
14         }
15     }
16     return result;
17 }

View Code

3. 中序

同样，对于中序也可以用后序那种模板式的代码来改写。改写版代码如下：

 1 class Solution
 2 {
 3 public:
 4     vector<int> inorderTraversal(TreeNode* root)
 5     {
 6         vector<int> answer;
 7         stack<pair<TreeNode*,int>> s;
 8         s.push(make_pair(root,0));
 9         while(!s.empty())
10         {
11             TreeNode* now=s.top().first;
12             if(now==NULL)
13                 s.pop();
14             else
15             {
16                 switch(s.top().second++)
17                 {
18                     case 0:
19                         s.push(make_pair(now->left,0));
20                         break;
21                     case 1:
22                         s.pop();
23                         answer.push_back(now->val);
24                         s.push(make_pair(now->right,0));
25                         break;
26                 }
27             }
28         }
29         return answer;
30     } 
31 };

View Code

【递归版】

 1 class Solution
 2 {
 3 public:
 4     vector<int> inorderTraversal(TreeNode* root)
 5     {
 6         vector<int> answer;
 7         helper(root,answer);
 8         return answer;
 9     }
10     void helper(TreeNode* root,vector<int> &answer)
11     {
12         if(root!=NULL)
13         {
14             helper(root->left,answer);
15             answer.push_back(root->val);
16             helper(root->right,answer);
17         }
18     }
19 };

View Code

【Divide & Conquer版】（在树相关的问题中更常用）

preorder:

 1 class Solution {
 2 public:
 3     vector<int>    preorderTraversal(TreeNode* root) {
 4         vector<int> result;
 5         if (root == NULL) {
 6             return result;
 7         }
 8 
 9         // Divide
10         vector<int> left = preorderTraversal(root->left);
11         vector<int> right = preorderTraversal(root->right);
12         
13         // Conquer
14         result.push_back(root->val);
15         result.insert(result.end(), left.begin(), left.end());
16         result.insert(result.end(), right.begin(), right.end());
17         return result;
18     }
19 };

View Code

Morris版

二、N-Queens

 1 class Solution
 2 {
 3 public:
 4     vector<vector<string>> solveNQueens(int n)
 5     {
 6         vector<vector<string>> result;
 7         N=n;
 8         columns=vector<int>(n,0);
 9         anti_diag=vector<int>(2*n,0);
10         main_diag=vector<int>(2*n,0);
11         C=vector<int>(n,0);
12         dfs(result,0);
13         return result;
14     }
15 private:
16     vector<int> columns;
17     vector<int> main_diag;
18     vector<int> anti_diag;
19     vector<int> C;
20     int N;
21 
22     void dfs(vector<vector<string>> &result,int row)//如果把result也定义在class里当成员变量，那dfs就只用row一个参数就行了。
23     {
24         if(row==N)
25         {
26             vector<string> tmp;
27             for(int i=0;i<N;i++)
28             {
29                 string str(N,'.');
30                 str[C[i]]='Q';
31                 tmp.push_back(str);
32             }
33             result.push_back(tmp);
34             return;
35         }
36         for(int j=0;j<N;j++)
37         {
38             bool ok=columns[j]==0 && anti_diag[j+row]==0 && main_diag[row-j+N]==0;
39             if(!ok) continue;
40             C[row]=j;
41             columns[j]=anti_diag[row+j]=main_diag[row-j+N]=1;
42             dfs(result,row+1);
43             columns[j]=anti_diag[row+j]=main_diag[row-j+N]=0;
44         }
45     }
46 };

View Code

需要注意的：除了每条横线、竖线上不能有1个以上的queen之外，斜线上也不能有1个以上的queen。

斜线具体需要分为平行于主对角线的这2n-1条线和平行于反对角线的2n-1条线。

对于平行于主对角线main_diag的这些斜线上的点而言，行与列之和(row+j)是定值，其和分布在0~2N-2。

对于平行于反对角线anti_diag的这些斜线上的点而言，行与列之差(row-j)是定值，其差分布在-(N-1)~(N-1)。为了将其转换为数组下标方便计算，将其加上N,这样就转换为分布在1~2N-1.

在写N皇后问题的dfs函数时意识到，其实有时候dfs里的参数很多主要是因为这些变量是定义在主角函数里的（比如这里的solveNQueens）。如果把这些变量都定义在class里面（通常放到private区域里），dfs就不用传这么多参数了。

Explanation

N-Queens II

 1 class Solution
 2 {
 3 public:
 4     int totalNQueens(int n)
 5     {
 6         N=n;
 7         columns=vector<int>(n,0);
 8         anti_diag=vector<int>(2*n,0);
 9         main_diag=vector<int>(2*n,0);
10         C=vector<int>(n,0);
11         int count=0;
12         dfs(count,0);
13         return count;
14     }
15 private:
16     vector<int> columns;
17     vector<int> main_diag;
18     vector<int> anti_diag;
19     vector<int> C;
20     int N;
21     //int count=0;
22     void dfs(int &count,int row)
23     {
24         if(row==N)
25         {
26             count++;
27             return;        
28         }
29         for(int j=0;j<N;j++)
30         {
31             bool ok=columns[j]==0 && anti_diag[row+j]==0 && main_diag[row-j+N]==0;
32             if(!ok) continue;
33             columns[j]=anti_diag[j+row]=main_diag[row-j+N]=1;
34             C[row]=j;
35             dfs(count,row+1);
36             columns[j]=anti_diag[row+j]=main_diag[row-j+N]=0;
37         }
38     }
39 };

View Code

需要注意的是，if(!ok)时应当continue，不是return。

三、

1. Maximum Depth of Binary Tree

[Divide & Conquer 版本][推荐]

 1 class Solution {
 2 public:
 3     int maxDepth(TreeNode* root) {
 4         if (root == NULL) {
 5             return 0;
 6         }
 7         int left = maxDepth(root->left);
 8         int right = maxDepth(root->right);
 9         return max(left, right) + 1;
10     }
11 };

View Code

[简洁版本] 时间复杂度 O(n), 空间复杂度O(logn)

1 class Solution
2 {
3 public:
4     int maxDepth(TreeNode* root)
5     {
6         if(root==NULL) return 0;
7         return max(maxDepth(root->left),maxDepth(root->right))+1;
8     }
9 };

View Code

[模版式dfs版本]

 1 class Solution
 2 {
 3 public:
 4     int maxDepth(TreeNode* root)
 5     {
 6         if(!root) return 0;
 7         helper(root,1);
 8         return max;
 9     }
10 private:
11     int max=0;
12     void helper(TreeNode* root, int count)
13     {
14         if(root==NULL)
15         {
16             if(count-1>max)
17                 max=count-1;
18             return;
19         }    
20         helper(root->left,count+1);
21         helper(root->right,count+1);
22     }
23 };

View Code

非递归版：基于前序遍历的基础之上，加上一个记录各节点高度的unordered_map和一个变量max即可。（所以说，熟练掌握树的非递归遍历后，可以在其基础上略加修改即可达到很多其他要求。）

 1 class Solution
 2 {
 3 public:
 4     int maxDepth(TreeNode* root)
 5     {
 6         if(!root) return 0;
 7         stack<TreeNode*> s;
 8         s.push(root);
 9         unordered_map<TreeNode*,int> umap;
10         umap[root]=1;
11         while(!s.empty())
12         {
13             TreeNode* now=s.top();
14             s.pop();
15             if(now!=NULL)
16             {
17                 if(!now->left && !now->right)
18                 {
19                     if(umap[now]>max)
20                         max=umap[now];
21                 }
22                 s.push(now->right);
23                 if(now->right!=NULL)//可删掉，不影响
24                     umap[now->right]=umap[now]+1;
25                 s.push(now->left);
26                 if(now->left!=NULL)//可删掉，不影响
27                     umap[now->left]=umap[now]+1;
28             }
29         }
30         return max;
31     }
32 private:
33     int max=0;
34 };

View Code

2. Minimum Depth of Binary Tree

递归版：

[模版式版本]

 1 class Solution
 2 {
 3 public:
 4     int minDepth(TreeNode* root)
 5     {
 6         if(root==NULL) return 0;
 7         helper(root,1);
 8         return minD;
 9     }
10 private:
11     int minD=INT_MAX;
12     void helper(TreeNode* root,int count)
13     {
14         if(!root->left && !root->right)
15         {
16             if(count<minD)
17                 minD=count;
18             return;
19         }
20         if(root->left)
21             helper(root->left,count+1);        
22         if(root->right)
23             helper(root->right,count+1);
24     }
25 };

View Code

注意：求minDepth时有很多小细节容易忽略和写错，要多注意。maxDepth里可以通过求所有NULL节点的上一层的高度的最大值来作为maxD，但是minDepth不能用此法，因为一个节点的最小高度不等于min(minDepth(root->left),minDepth(root->right))+1（）

update 8.10:

 1 class Solution {
 2 public:
 3     int minDepth(TreeNode* root) {
 4         if (root == NULL) {
 5             return 0;
 6         }
 7         return getMin(root);
 8     }
 9     int getMin(TreeNode* root) {
10         if (root == NULL) {
11             return INT_MAX;
12         }
13         if (root->left == NULL && root->right == NULL) {
14             return 1;
15         }
16         return min(getMin(root->left), getMin(root->right)) + 1;
17     }
18 };

View Code

这里用了一个trick。若root==NULL,则视为其minDepth是INT_MAX。通过这种方式来忽略那些只有左子树或只有右子树为空的节点的干扰。

非递归版：（与求maxDepth的大体类似）

 1 class Solution
 2 {
 3 public:
 4     int minDepth(TreeNode* root)
 5     {
 6         if(root==NULL) return 0;
 7         stack<TreeNode*> s;
 8         s.push(root);
 9         unordered_map<TreeNode*,int> umap;
10         umap[root]=1;
11         int minD=INT_MAX;
12         while(!s.empty())
13         {
14             TreeNode* now=s.top();
15             s.pop();
16             if(now!=NULL)
17             {
18                 if(!now->left && !now->right)    
19                 {
20                     if(umap[now]<minD)
21                         minD=umap[now];
22                 }
23                 s.push(now->right);
24                 umap[now->right]=umap[now]+1;
25                 s.push(now->left);
26                 umap[now->left]=umap[now]+1;
27             }
28         }
29         return minD;
30     }
31 };

View Code

四、

1. Same Tree

 1 class Solution {
 2 public:
 3     bool isSameTree(TreeNode* p,TreeNode* q)
 4     {
 5         if(p==NULL && q==NULL)
 6             return true;
 7         if(p==NULL || q==NULL) //能运行到这说明上个if的判定不成立，即p和q并不都为NULL.当一个为NULL一个不为NULL时,说明结构不同，即不相等。
 8             return false;
 9         if(p->val!=q->val)
10             return false;
11         return isSameTree(p->left,q->left) && isSameTree(p->right,q->right);
12     }
13 };

View Code

2. Symmetric Tree

这里面直接就调用了same tree的代码（微加修改），isSameTree函数的改动之处就在于最后是p的left与q的right比较，p的right与q的left比较。

 1 class Solution
 2 {
 3 public:
 4     bool isSymmetric(TreeNode* root)
 5     {
 6         if(root==NULL) return true;
 7         return isSameTree(root->left,root->right);
 8     }
 9 private:
10     bool isSameTree(TreeNode* p,TreeNode* q)
11     {
12         if(p==NULL && q==NULL) return true;
13         if(p==NULL || q==NULL) return false;
14         if(p->val!=q->val) return false;
15         return isSameTree(p->left,q->right)&&isSameTree(p->right,q->left);//left和right比较
16     }
17 };

View Code

五、

1. Populating Next Right Pointers in Each Node

 1 class Solution
 2 {
 3 public:
 4     void connect(TreeLinkNode* root)
 5     {
 6         if(root==NULL) return;
 7         if(root->left!=NULL)
 8             root->left->next=root->right;
 9         if(root->right!=NULL)
10             root->right->next=root->next==NULL?NULL:root->next->left;
11         connect(root->left);
12         connect(root->right);
13     }
14 };

View Code

2. Populating Next Right Pointers in Each Node II

 1 class Solution
 2 {
 3 public:
 4     void connect(TreeLinkNode* root)
 5     {
 6         TreeLinkNode* tempChild=new TreeLinkNode(0);
 7         while(root)//root从上到下遍历每一层（纵向）
 8         {
 9             TreeLinkNode* cur=tempChild;
10             while(root)//root从左到右遍历某个特定的层（横向）
11             {
12                 if(root->left){cur->next=root->left;cur=cur->next;}    
13                 if(root->right){cur->next=root->right;cur=cur->next;}
14                 root=root->next;//root向右移动
15             }
16             root=tempChild->next;//root跳到下一层
17             tempChild->next=NULL;
18         }    
19     }
20 };

View Code

六、

1. Convert Sorted Array to Binary Search Tree

 1 class Solution
 2 {
 3 public:
 4     TreeNode* sortedArrayToBST(vector<int>& num)
 5     {
 6         return helper(num,0,num.size()-1);
 7     }
 8 private:
 9     TreeNode* helper(vector<int> &num,int start,int end)
10     {
11         if(start>end) return NULL;
12         int mid=start+(end-start)/2;
13         TreeNode* root=new TreeNode(num[mid]);
14         root->left=helper(num,start,mid-1);
15         root->right=helper(num,mid+1,end);
16         return root;
17     }
18 };

View Code

值得注意的是，如果把helper参数列表里的vector<int> &num的引用去掉，变成vector<int> num, 那么会发生TLE. 所以在用vector之类的容器时加引用还是很重要的。

2. Convert Sorted List to Binary Search Tree

 1 class Solution
 2 {
 3 public:
 4     TreeNode* sortedListToBST(ListNode* head)
 5     {
 6         int count=calLen(head);    
 7         return helper(head,0,count-1);    
 8     }
 9 private:
10     int calLen(ListNode* head)
11     {
12         int count=0;
13         while(head!=NULL)
14         {    
15             head=head->next;
16             count++;
17         }
18         return count;
19     }
20     TreeNode* helper(ListNode* head, int start, int end)
21     {
22         if(start>end) return NULL;
23         int mid=start+(end-start)/2;
24         ListNode *p=head;
25         for(int i=start;i<mid;i++)    
26             p=p->next;
27         TreeNode* root=new TreeNode(p->val);
28         root->left=helper(head,start,mid-1);
29         root->right=helper(p->next,mid+1,end);
30         return root;
31     }
32 };

View Code

注意细节问题。

ref:remlostime

七、Balanced Binary Tree

code 1: Divide & Conquer

 1 class Solution {
 2 public:
 3     bool isBalanced(TreeNode* root) {    
 4         return maxDepth(root) != -1;
 5     }
 6     int maxDepth(TreeNode* root) {
 7         if (root == NULL) {
 8             return 0;
 9         }
10         int left = maxDepth(root->left);
11         int right = maxDepth(root->right);
12         if (left == -1 || right == -1 || abs(left - right) > 1) {
13             return -1;
14         }
15         return max(left, right) + 1;
16     }
17 };

View Code

code 2:

 1 class Solution
 2 {
 3 public:
 4     bool isBalanced(TreeNode* root)
 5     {
 6         if(!root) return true;
 7         return (isBalanced(root->left) && isBalanced(root->right) && balancedNode(root));
 8     }
 9 private:
10     bool balancedNode(TreeNode* root)
11     {
12         int dif=height(root->left)-height(root->right);
13         if(dif>=-1 && dif<=1) return true;
14         else return false;
15     }
16     int height(TreeNode* root)
17     {
18         if(root==NULL) return 0;
19         return(max(height(root->left),height(root->right))+1);
20     }
21 };

View Code

八、

1. Sum Root to Leaf Numbers

非递归版本：

 1 class Solution
 2 {
 3 public:
 4     int sumNumbers(TreeNode* root)
 5     {
 6         if(root==NULL) return 0;
 7         postorderTraversal(root);
 8         return result;
 9     }
10 private:
11     int result=0;
12     void postorderTraversal(TreeNode* root)
13     {
14         stack<pair<TreeNode*,int>> s;
15         s.push(make_pair(root,0));    
16         string str;
17         while(!s.empty())
18         {
19             TreeNode* now=s.top().first;
20             if(now==NULL) s.pop();
21             else
22             {
23                 switch(s.top().second++)
24                 {
25                     case 0:
26                         str+=to_string(now->val);
27                         s.push(make_pair(now->left,0));    
28                         break;
29                     case 1:
30                         s.push(make_pair(now->right,0));
31                         break;
32                     case 2:
33                         s.pop();
34                         if(!now->left && !now->right)
35                             result+=stoi(str);
36                         str.resize(str.size()-1);
37                         break;
38                         
39                 }
40             }
41         }
42     }
43 };

View Code

利用后序遍历，在每次第3次遇到一个节点(case:2) 且该节点为叶子节点时，使result累加上此时过往路径对应的整数（其实这里的过往路径相当于遍历一遍当前栈内元素）。

递归版本还没理解好，先放在这。

 1 class Solution {
 2 public:
 3     int sumNumbers(TreeNode *root) {
 4         return dfs(root, 0);
 5     }
 6 private:
 7     int dfs(TreeNode *root, int sum) {
 8         if (root == nullptr) return 0;
 9         if (root->left == nullptr && root->right == nullptr)
10             return sum * 10 + root->val;
11         return dfs(root->left, sum*10 + root->val) + dfs(root->right, sum*10 + root->val);
12     }
13 };

View Code

2. Path Sum

非递归版本：（和上题类似，只不过计算path sum的方式不同。）

 1 class Solution
 2 {
 3 public:
 4     bool hasPathSum(TreeNode* root,int sum)
 5     {
 6         return postorderTraversal(root,sum);
 7     }
 8 private:
 9     int tmp=0;
10     bool postorderTraversal(TreeNode* root,int target)
11     {
12         stack<pair<TreeNode*,int>> s;
13         s.push(make_pair(root,0));
14         string str;
15         while(!s.empty())
16         {
17             TreeNode* now=s.top().first;
18             if(now==NULL)
19                 s.pop();
20             else
21             {
22                 switch(s.top().second++)
23                 {
24                     case 0:
25                         tmp+=now->val;
26                         s.push(make_pair(now->left,0));
27                         break;
28                     case 1:
29                         s.push(make_pair(now->right,0));
30                         break;
31                     case 2:
32                         s.pop();
33                         if(!now->left && !now->right) 
34                             if(tmp==target)
35                                 return true;
36                         tmp-=now->val;
37                         break;
38                 }
39             }
40         }
41         return false;
42     }
43 };

View Code

递归版本：（再理解一下）

1 class Solution {
2 public:
3     bool hasPathSum(TreeNode *root, int sum) {
4         if (root == NULL) return false;
5         if (root->left == NULL && root->right == NULL) // leaf
6           return sum == root->val;
7         return hasPathSum(root->left, sum - root->val) || hasPathSum(root->right, sum - root->val);
8     }
9 };

View Code

写递归程序主要就是看递归出口以及如何缩小规模变成一个完全一样只是规模略小的子问题。

像这里就是由求root为根的一颗子树的hasPathSum转换为求分别以root->left和root->right为根的两颗子树的hasPathSum，其中target相应的减去root->val。

递归出口就是对于leaf节点（左右子树都为空）和NULL节点的处理情况。

update 8.10

1 bool hasPathSum(TreeNode* root, int sum) {
2     if (root == NULL) {
3         return false;
4     }
5     if (root->left == NULL && root->right == NULL && root->val == sum) {
6         return true;
7     }
8     return (hasPathSum(root->left, sum - root->val) || hasPathSum(root->right, sum - root->val));
9 }

View Code

递归-模板化版本：（personal style）

 1 class Solution
 2 {
 3 public:
 4     bool hasPathSum(TreeNode* root,int sum)
 5     {
 6         return helper(root,sum);
 7     }
 8     bool helper(TreeNode* root,int target)
 9     {
10         if(root==NULL) return false;
11         if(root->left==NULL && root->right==NULL) 
12             return root->val==target;
13         return helper(root->left,target-root->val)||helper(root->right,target-root->val);
14     }
15 };

View Code

3. Path Sum II

非递归版本：（非递归用起来确实很方便，但是递归版本必须要熟练掌握）

 1 class Solution
 2 {
 3 public:
 4     vector<vector<int>> pathSum(TreeNode* root,int sum)
 5     {
 6         vector<vector<int>> result;
 7         postorderTraversal(root,result,sum);
 8         return result;
 9     }
10     void postorderTraversal(TreeNode* root, vector<vector<int>> &result,int target)
11     {
12         stack<pair<TreeNode*,int>> s;
13         s.push(make_pair(root,0));
14         vector<int> tmp;
15         int sum=0;
16         while(!s.empty())
17         {
18             TreeNode* now=s.top().first;
19             if(now==NULL) s.pop();
20             else
21             {
22                 switch(s.top().second++)
23                 {
24                     case 0:
25                         tmp.push_back(now->val);
26                         sum+=now->val;
27                         s.push(make_pair(now->left,0));
28                         break;
29                     case 1:
30                         s.push(make_pair(now->right,0));
31                         break;
32                     case 2:
33                         s.pop();
34                         if(!now->left&&!now->right)
35                         {
36                             if(sum==target)
37                                 result.push_back(tmp);
38                         }
39                         sum-=now->val;
40                         tmp.pop_back();
41                         break;
42                 }
43             }
44         }
45     }
46 };

View Code

递归版本：

 1 class Solution {
 2 public:
 3     vector<vector<int>> pathSum(TreeNode* root,int sum)
 4     {
 5         vector<vector<int>> result;
 6         helper(result,root,sum);
 7         return result;
 8     }
 9     void helper(vector<vector<int>> &result,TreeNode* root,int target)
10     {
11         if(root==NULL) return;
12         tmp.push_back(root->val);
13         if(root->left==NULL && root->right==NULL)
14         {
15             if(root->val==target)
16                 result.push_back(tmp);    
17         }
18         helper(result,root->left,target-root->val);
19         helper(result,root->right,target-root->val);
20         tmp.pop_back();
21     }
22     vector<int> tmp;
23 };

View Code

九、Flatten Binary Tree to Linked List

这道题目要求有说in-place, 怎么样算in-place?

非递归版本：

 1 class Solution
 2 {
 3 public:
 4     void flatten(TreeNode* root)
 5     {
 6         preorderTraversal(root);
 7     }
 8     void preorderTraversal(TreeNode* root)
 9     {
10         if(root==NULL) return;
11         stack<TreeNode*> s;
12         s.push(root);
13         while(!s.empty())
14         {
15             TreeNode* now=s.top();
16             s.pop();
17             if(now!=NULL)
18             {//必须要确保压入栈的只能是非NULL的，否则会影响到now->right的指向。now->right只能指向节点，不能是NULL(除非是最后一个节点)。
19                 if(now->right!=NULL)
20                     s.push(now->right);    
21                 if(now->left!=NULL)
22                     s.push(now->left);
23                 now->left=NULL;
24                 if(!s.empty())//检查一下是否栈非空，因为要用到s.top().(毕竟上次判断完非空后有pop操作)
25                     now->right=s.top();
26             }
27         }
28     }
29 };

View Code

非递归版本在先序遍历的基础上有一些细节改动，主要是需要确保入栈的只能是非NULL节点。

递归版本：

一开始没有思路，后来看了code ganker的讲解和该博客的代码，原来只需要保存一个pre即可。

 1 class Solution
 2 {
 3 public:
 4     void flatten(TreeNode* root)
 5     {
 6         helper(root,NULL);
 7     }
 8     TreeNode* helper(TreeNode* root,TreeNode* pre)
 9     {
10         if(root==NULL) return pre;
11         if(pre!=NULL)
12             pre->right=root;
13         pre=root;//每访问一个节点，pre就指向该节点。
14         TreeNode* left=root->left;
15         root->left=NULL;
16         TreeNode* right=root->right;
17         pre=helper(left,pre);
18         pre=helper(right,pre);
19         return pre;
20     }
21 };

View Code

本质上是在前序遍历的递归代码基础上改的。每遍历一个节点，pre都会更新并指向该节点。所以倒数第3行中pre=helper(left,pre); 执行完后，pre的值即为先序遍历root的左子树的最后一个点。这个需要注意一下，加深理解。

十、

1. Construct Binary Tree from Preorder and Inorder Traversal

 1 class Solution
 2 {
 3 public:
 4     TreeNode* buildTree(vector<int> &preorder,vector<int> &inorder)
 5     {
 6         int len=preorder.size();
 7         return helper(preorder,0,len-1,inorder,0,len-1);
 8     }
 9     TreeNode* helper(vector<int> &preorder,int s1,int e1,vector<int>& inorder,int s2,int e2)
10     {
11         if(s1>e1||s2>e2) return NULL;
12         TreeNode* node=new TreeNode(preorder[s1]);
13         int index=find(inorder,node->val);
14         node->left=helper(preorder,s1+1,index-s2+s1,inorder,s2,index-1);
15         node->right=helper(preorder,index-s2+s1+1,e1,inorder,index+1,e2);
16         return node;
17     }
18     int find(vector<int> &inorder,int x)
19     {
20         for(int i=0;i<inorder.size();i++)
21         {
22             if(inorder[i]==x)
23                 return i;
24         }
25         return -1;
26     }
27 };

View Code

需要注意Line14,15的递归下标别写错。

2. Construct Binary Tree from Inorder and Postorder Traversal

 1 class Solution
 2 {
 3 public:
 4     TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder)
 5     {
 6         int len=inorder.size();
 7         return helper(inorder,0,len-1,postorder,0,len-1);
 8     }
 9     TreeNode* helper(vector<int> &inorder,int s1,int e1,vector<int> &postorder,int s2,int e2)
10     {
11         if(s1>e1||s2>e2) return NULL;//别忘了递归出口
12         TreeNode* node=new TreeNode(postorder[e2]);
13         int index=find(inorder,node->val);
14         node->left=helper(inorder,s1,index-1,postorder,s2,index-1-s1+s2);
15         node->right=helper(inorder,index+1,e1,postorder,index-s1+s2,e2-1);
16         return node;
17     }
18     int find(vector<int> &inorder,int x)
19     {
20         for(int i=0;i<inorder.size();i++)
21             if(inorder[i]==x) return i;
22         return -1;
23     }
24 };

View Code

写递归函数不要忘了写递归出口。

十一、Binary Tree Right Side View

用BFS非递归做的。但是代码有点繁琐。

而且，需要掌握一下递归做法。

 1 class Solution
 2 {
 3 public:
 4     vector<int> rightSideView(TreeNode* root)
 5     {
 6         vector<int> result; 
 7         if(!root) return result;
 8         queue<pair<TreeNode*,int>> q;
 9         q.push(make_pair(root,1));
10         TreeNode* pre=root;
11         int preLevel=1;
12         while(!q.empty())
13         {
14             TreeNode* now=q.front().first;
15             if(preLevel!=q.front().second)
16                 result.push_back(pre->val);
17             if(now->left==NULL&&now->right==NULL&&q.size()==1)
18                 result.push_back(now->val);
19             preLevel=q.front().second;
20             pre=now;
21             q.pop();
22             if(now->left!=NULL)
23                 q.push(make_pair(now->left,preLevel+1));
24             if(now->right!=NULL)
25                 q.push(make_pair(now->right,preLevel+1));        
26         }
27         return result;
28     }
29 };

View Code

十二、Recover Binary Search Tree

递归版本：

 1 class Solution
 2 {
 3 public:
 4     void recoverTree(TreeNode* root)
 5     {
 6         helper(root);
 7         int tmp=p1->val;
 8         p1->val=p2->val;    
 9         p2->val=tmp;
10     }
11     void helper(TreeNode* root)
12     {
13         if(root==NULL) return;
14         helper(root->left);
15         if(pre>root->val && flag==0)
16         {
17             flag=1;
18             p1=prePtr;    
19             p2=root;
20         }
21         else if(pre>root->val && flag==1)
22             p2=root;
23         pre=root->val;
24         prePtr=root;
25         helper(root->right);
26     }
27     int pre=INT_MIN;
28     TreeNode* p1=NULL,*p2=NULL;
29     TreeNode* prePtr=NULL;
30     int flag=0;
31 };

View Code

一个重要的特性就是，在本应递增的序列里，如果有两个值x1,x2发生了互换，那么会有两种情况：

case1:两个值不相邻

那么第1次出现left>right的地方，这里的left即为x1.（因为它本应在后面，是大值，现在换到前面来必然导致它大于其右侧的数字）。应用pre指针记录下这个left对应节点。

第2次出现left>right的地方，这里的right即为x2.（同理）。

case2：两个值相邻。则只会出现1次left>right的地方。

所以，综合case1和case2，在第一次遇到left>right时就把left和right分别标记为p1,p2，这样不管会不会有第2次left>right都无所谓，当有第2次left>right时只需更新一下p2即可。

改天把非递归版本补上。

十三、Clone Graph

 1 class Solution
 2 {
 3 public:
 4     typedef UndirectedGraphNode UGNode;
 5     UndirectedGraphNode* cloneGraph(UndirectedGraphNode* node)
 6     {
 7         if(node==NULL) return NULL;
 8         return dfs(node);
 9     }
10     UGNode* dfs(UGNode* node)
11     {
12         UGNode* p=new UGNode(node->label);
13         umap[p->label]=p;//注意，这里对umap赋值只能是p不能是node，因为在下面加入p的邻居时会用到。
14         for(int i=0;i<node->neighbors.size();i++)
15         {
16             if(umap.find(node->neighbors[i]->label)==umap.end())
17                 p->neighbors.push_back(dfs(node->neighbors[i]));
18             else
19                 p->neighbors.push_back(umap[node->neighbors[i]->label]);
20         }    
21         return p;
22     }
23     unordered_map<int,UGNode*> umap;
24 };

View Code

需要注意的是，在return时应该是return的新建的copy指针，而不是原来图中的指针。

十四、Number of Islands

简洁版：

 1 class Solution
 2 {
 3 public:
 4     int numIslands(vector<vector<char>> &grid)
 5     {
 6         if(grid.size()==0 || grid[0].size()==0) return 0;
 7         m=grid.size();
 8         n=grid[0].size();
 9         for(int i=0;i<m;i++)
10         {
11             for(int j=0;j<n;j++)
12             {
13                 if(grid[i][j]=='1')
14                 {
15                     count++;
16                     dfs(grid,i,j);
17                 }
18             }
19         }
20         return count;
21     }
22     int count=0;
23     int m,n;
24     void dfs(vector<vector<char>> &grid,int i,int j)
25     {
26         if(i<0 || j<0 || i>=m || j>=n) return;
27         if(grid[i][j]!='1') return;
28         grid[i][j]='2';
29         dfs(grid,i+1,j);
30         dfs(grid,i-1,j);
31         dfs(grid,i,j+1);
32         dfs(grid,i,j-1);
33     }
34 };

View Code

这里利用一个trick，就是访问过的'1'都改为’2‘，这样就不用再分配一个visited数组了，节省点空间。

啰嗦版，可无视之：

 1 class Solution
 2 {
 3 public:
 4     int numIslands(vector<vector<char>> &grid)
 5     {
 6         m=grid.size();
 7         if(m==0) return 0;
 8         n=grid[0].size();
 9         visited=vector<vector<int>>(m,vector<int>(n,0));
10         sumOfOnes=calOnes(grid);
11         for(int i=0;i<m;i++)
12         {
13             for(int j=0;j<n;j++)
14             {
15                 if(visited[i][j]==0 && grid[i][j]=='1')
16                 {
17                     count++;
18                     dfs(grid,i,j);
19                 }    
20             }
21         }
22         return count;
23     }
24 private:
25     int m, n;
26     int count=0;
27     int sumOfOnes=0;
28     int countOnes=0;
29     vector<vector<int>> visited;
30     void dfs(vector<vector<char>> &matrix,int row,int col)
31     {
32         countOnes++;
33         visited[row][col]=1;
34         if(countOnes>=sumOfOnes)            
35             return;
36         if(row+1<m && matrix[row+1][col]=='1' && !visited[row+1][col])
37             dfs(matrix,row+1,col);
38         if(col+1<n && matrix[row][col+1]=='1' && !visited[row][col+1])
39             dfs(matrix,row,col+1);
40         if(row-1>=0 && matrix[row-1][col]=='1' && !visited[row-1][col])
41             dfs(matrix,row-1,col);
42         if(col-1>=0 && matrix[row][col-1]=='1' && !visited[row][col-1])
43             dfs(matrix,row,col-1);
44     }
45     int calOnes(vector<vector<char>> &matrix)
46     {
47             int count=0;
48             for(int i=0;i<m;i++)
49             {
50                 for(int j=0;j<n;j++)
51                 {
52                     if(matrix[i][j]=='1')
53                         count++;
54                 }
55             }
56             return count;
57     }
58 };

View Code

一开始犯了很多小错误。比如，只向右和向下搜索，并以访问右下角元素作为递归出口。这是不对的，因为如果遍历的时候第一次遇到的1是第一行最后一个，那就只能遍历最后一列了。

参考别的答案后发现我的略繁琐，不简洁。

十五、Binary Tree Maximum Path Sum

code1: 分治 [new]

 1 class Solution {
 2 public:
 3     int maxPathSum(TreeNode* root) {
 4         int res = INT_MIN;
 5         maxPath(root, res);
 6         return res;
 7     }
 8     int maxPath(TreeNode* root, int &res) {
 9         if (root == NULL) {
10             return 0;
11         }
12         int left = max(0, maxPath(root->left, res));
13         int right = max(0, maxPath(root->right, res));
14         res = max(res, left + right + root->val);
15         return max(left, right) + root->val;
16     }
17 };

View Code

该题利用一个特点：任何一个path都是先升、后降，一旦降了就不能再升了（只升或只降可以看作特例）。因此每个path都有一个最高点。

所以，函数maxPath(node)可以定义为最高点为node的情况下所能取到的最大和。[注意，这里也能体现一个情况，就是分治函数往往返回值就是结果，dfs函数往往返回值是void]

几个需要解释的点：

这个maxPath函数在Line15返回的是以root为最高点单边儿所能取到的最大值，即不带拱的（只能从root往左或只能从root往右，不能带拱）。

而Line14里 left + right + root->val 是指的以当前点为最高点的允许带拱的情况下有可能取到的最大值。

reference

//刚才写又忘了写递归出口了。小细节、corner case 很重要！！！

code2:

 1 class Solution
 2 {
 3 public:
 4     int maxPathSum(TreeNode* root)
 5     {
 6         dfs(root);    
 7         return maxNum;
 8     }
 9     int maxNum=INT_MIN;
10     int dfs(TreeNode* root)
11     {//每个dfs里默认是求sum一定会带上root的
12         if(root==NULL) return 0;
13         int l=dfs(root->left);
14         int r=dfs(root->right);
15         int sum=root->val;
16         if(l>0) sum+=l;
17         if(r>0) sum+=r;
18         maxNum=max(maxNum,sum);
19         return max(l,r)>0?root->val+max(l,r):root->val;//须格外注意
20     }
21 };

View Code

refer to soulMach. 代码默认是每次执行dfs函数时都必须把该节点带上来算入sum。

在最后返回时需要注意，该节点是被其父节点调用的，所以返回的时候不能有分叉，即只能返回一个让父节点遍历下来时不会发生分叉的情况，因此不能让sum把left和right都加上，最多加一个。

十六、Validate Binary Search Tree

 1 class Solution
 2 {
 3 public:
 4     bool isValidBST(TreeNode* root)
 5     {
 6         inorder(root);    
 7         if(flag==1) return false;
 8         else return true;
 9     }
10 private:
11     void inorder(TreeNode* root)
12     {
13         if(root==NULL) return;
14         inorder(root->left);
15         if(!firstNode && pre>=root->val) 
16             flag=1;
17         firstNode=0;
18         pre=root->val;
19         inorder(root->right);
20     }
21     int pre=INT_MIN;
22     int flag=0;
23     int firstNode=1;
24 };

View Code

我这代码看起来并不美观。第一次写时掉进去一个很隐蔽的坑：第一个节点的value就是INT_MIN。由于过度rely on INT_MIN，导致这个test case过不了。后来就专门加了个flag：firstNode，使得对第一个节点不置flag=1。不过很不美观。

更美观的做法是不用一个int值的pre，改为用TreeNode* pre.这样可令其初值为NULL，作为对第一个节点的判断依据。代码可参考此。

BST的充要条件是：中序遍历序列是升序序列。

--26 problems in all

============================================================================================================

树相关

backtracking相关

dfs相关

图的遍历相关

nowcoder related

cc150 related