LeetCode

LeetCode树模板

TreeNode

1 struct TreeNode {
2     int val;
3     TreeNode *left;
4     TreeNode *right;
5     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
6 };

先序遍历

 1 void visitALongLeftBranch(TreeNode* x, stack<TreeNode*> &s)
 2 {
 3     while (x)
 4     {
 5         //x->visit();
 6         s.push(x->right);
 7         x = x->left;
 8     }
 9 }
10 
11 void travPre_3(TreeNode* x)
12 {
13     stack<TreeNode*> s;
14     while (true)
15     {
16         visitALongLeftBranch(x, s);
17         if (s.empty()) break;
18         x = s.top();
19         s.pop();
20     }
21 }

层序遍历

 1 void travLevel()
 2 {
 3     queue<TreeNode *> q;
 4     q.push(root);
 5     while (!q.empty())
 6     {
 7         TreeNode *x = q.front();
 8         q.pop();
 9         //x->visit();
10         if (x->HasLChild()) q.push(x->left);
11         if (x->HasRChild()) q.push(x->right);
12     }
13 }

中序遍历

 1 void goAlongLeftBranch(TreeNode *x, stack<TreeNode *> &s)
 2 {
 3     while (x)
 4     {
 5         s.push(x);
 6         x = x->left;
 7     }
 8 }
 9 
10 void travIn_2(TreeNode *x)
11 {
12     stack<TreeNode *> s;
13     while (true)
14     {
15         goAlongLeftBranch(x, s);
16         if (s.empty()) break;
17         x = s.top();
18         s.pop();
19         //x->visit();
20         x = x->right;
21     }
22 }

LeetCode 100 相同的树

这种递归形式几乎算是树的基本模板，三条件并列的尾递归。

 1 class Solution {
 2 public:
 3     bool isSameTree(TreeNode* p, TreeNode* q) {
 4         if(NULL==p&&NULL==q)
 5             return 1;
 6         if(NULL==p||NULL==q)
 7             return 0;
 8         return p->val==q->val && isSameTree(p->left,q->left) && isSameTree(p->right,q->right);
 9     }
10 };

LeetCode 101 对称二叉树

先序遍历一次左子树，交换先序遍历的左右子节点顺序遍历一次右子树，比较两次遍历得到的序列。

用不可能值填补NULL在序列中的位置。意外地不慢。

 1 class Solution {
 2 public:
 3     vector<int> res1;
 4     vector<int> res2;
 5     bool isSymmetric(TreeNode* root) {
 6         if(NULL==root)
 7             return 1;
 8         else
 9         {
10             if(NULL!=root->left||NULL!=root->right)
11             {
12                 travPre_l(root->left);
13                 travPre_r(root->right);
14                 return equal(res1,res2);
15             }
16             else 
17                 return 1;
18         }
19     }
20     void travPre_l(TreeNode* x)
21     {
22         
23          stack<TreeNode*> s;
24         while (true)
25         {
26             visitALongLeftBranch(x, s);
27             if (s.empty()) break;
28             x = s.top();
29             s.pop();
30         }
31     }
32     void travPre_r(TreeNode* x)
33     {
34          stack<TreeNode*> s;
35         while (true)
36         {
37             visitALongRightBranch(x, s);
38             if (s.empty()) break;
39             x = s.top();
40             s.pop();
41         }
42     }
43     void visitALongLeftBranch(TreeNode* x, stack<TreeNode*> &s)
44     {
45         while (x)
46         {
47             res1.push_back(x->val);
48             s.push(x->right);
49             x = x->left;
50         }
51         res1.push_back(-10991);
52     }
53     void visitALongRightBranch(TreeNode* x, stack<TreeNode*> &s)
54     {
55         while (x)
56         {
57             res2.push_back(x->val);
58             s.push(x->left);
59             x = x->right;
60         }
61         res2.push_back(-10991);
62     }
63     bool equal(vector<int> &a,vector<int> &b)
64     {
65         if(a.size()!=b.size())
66             return 0;
67         for(int i=0;i<a.size();++i)
68             if(a[i]!=b[i])
69                 return 0;
70         return 1;
71     }
72 };

更简洁的方法：

递归

 1 class Solution {
 2 public:
 3     bool isSymmetric(TreeNode* root) {
 4         return isMirror(root,root);
 5     }
 6     bool isMirror(TreeNode *t1,TreeNode *t2)
 7     {
 8         if (t1 == NULL && t2 == NULL) return 1;
 9         if (t1 == NULL || t2 == NULL) return 0;
10         return (t1->val == t2->val)&& isMirror(t1->right, t2->left)&& isMirror(t1->left, t2->right);
11     }
12 };

尾递归改写为迭代（辅助队列），略。

LeetCode 104 二叉树的最大深度

最僵硬的方法就是毫无意义地遍历一次，单纯为了数层数...慢得出奇...

 1 class Solution {
 2 public:
 3     int maxDepth(TreeNode* root) {
 4         int depth=0;
 5         vector<vector<int>> res;
 6         vector<int> ans;
 7         queue<TreeNode*> q;
 8         q.push(root);
 9         q.push(NULL);
10         while(!q.empty())
11         {
12             TreeNode* x=q.front();
13             q.pop();
14             if(x)
15             {
16                 ans.push_back(x->val);
17                 if (NULL!=x->left) q.push(x->left);
18                 if (NULL!=x->right) q.push(x->right);
19             }
20             else
21             {
22                 if(!ans.empty())
23                 {
24                     q.push(NULL);
25                     res.push_back(ans);
26                     ans.clear();
27                     depth++;
28                 }
29             }
30         }
31         return depth;
32     }
33 };

View Code

简洁的递归，BFS和DFS均能解

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

LeetCode 112 路径总和

DFS，简洁...

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

LeetCode 872 叶子相似的树

遍历到叶时加入序列

 1 class Solution {
 2 public:
 3     bool leafSimilar(TreeNode* root1, TreeNode* root2) {
 4         vector<int> res1;
 5         traverse(root1,res1);
 6         vector<int> res2;
 7         traverse(root2,res2);
 8         return res1==res2;
 9     }
10     void traverse(TreeNode* x,vector<int>& res)
11     {
12         if (NULL == x) return;
13         if(!x->left&&!x->right)
14             res.push_back(x->val);
15         traverse(x->left,res);
16         traverse(x->right,res);
17     }
18 };

总结

二叉树作为一种自带递归性质的数据结构，很多时候使用递归可以很让问题变得简单。

设置一个count逐个计数这种做法不仅代码冗长而且效率低下，可以说是非常缺乏递归的思想。

尾递归尽量改写为迭代形式，避免栈溢出。