树类型题

 1 // leetcodeTree.cpp : 定义控制台应用程序的入口点。
 2 //
 3 
 4 #include "stdafx.h"
 5 #include <iostream>
 6 #include <queue>
 7 #include <stack>
 8 #include <vector>
 9 
10 using namespace std;
11 
12 struct TreeNode {
13     int val;
14     TreeNode *left;
15     TreeNode *right;
16     TreeNode(int x) : val(x), left(nullptr), right(nullptr) { };
17 };
18 struct TreeLinkNode {
19     int val;
20     TreeLinkNode *left;
21     TreeLinkNode *right;
22     TreeLinkNode *next;
23     TreeLinkNode(int x) : val(x) { left = nullptr; right = nullptr; next = nullptr; };
24 };
25 
26 TreeNode* build(TreeNode *root, int val) {  // 构造一棵树
27     if (root == nullptr) {
28         root = new TreeNode(val);
29         return root;
30     }
31     if (val < root->val)
32         root->left = build(root->left, val);
33     else
34         root->right = build(root->right, val);
35 
36     return root;
37 }
38 
39 vector<int> preOrderTraversal(TreeNode *root) {  // 非递归先序遍历
40     vector<int> result;
41     stack<TreeNode*> stk;
42     if (root != nullptr)
43         stk.push(root);
44     while (!stk.empty()) {
45         TreeNode *p = stk.top();
46         stk.pop();
47         cout << ‘\t‘ << p->val;       // 打印遍历序列 
48         result.push_back(p->val);
49 
50         if (p->right != nullptr)       // 注意是先进栈右孩子，再进栈左孩子
51             stk.push(p->right);
52         if (p->left != nullptr)
53             stk.push(p->left);
54     }
55     return result;
56 }
57 
58 int main() {
59     int t[] = {5,4,3,6,7};
60     TreeNode* root = nullptr;
61     for(int i=0;i<sizeof(t)/sizeof(int);++i)  // build a tree
62         build(root,t[i]);
63         
64     preOrderTraversal(root);
65     
66     return 0; 
67 }

 1 vector<int> preOrderTraversal(TreeNode *root) {  // 非递归先序遍历
 2     vector<int> result;
 3     stack<TreeNode*> stk;
 4     if (root != nullptr)
 5         stk.push(root);
 6     while (!stk.empty()) {
 7         TreeNode *p = stk.top();
 8         stk.pop();
 9         cout << ‘\t‘ << p->val;
10         result.push_back(p->val);
11 
12         if (p->right != nullptr)       // 注意是先进栈右孩子，再进栈左孩子
13             stk.push(p->right);
14         if (p->left != nullptr)
15             stk.push(p->left);
16     }
17     return result;
18 }

 1 vector<int> inOrderTraversal(TreeNode *root) {  // 非递归中序遍历
 2     vector<int> result;
 3     stack<TreeNode*> stk;
 4     TreeNode *p = root;
 5 
 6     while (!stk.empty() || p != nullptr) {
 7         if (p != nullptr) {
 8             stk.push(p);
 9             p = p->left;
10         }
11         else {
12             p = stk.top();
13             stk.pop();
14             cout << ‘\t‘ << p->val;
15             result.push_back(p->val);
16             p = p->right;
17         }
18     }
19     return result;
20 }

 1 vector<int> postOrderTravelsal(TreeNode *root) {
 2     vector<int> result;
 3     stack<TreeNode*> stk;
 4     if (root == nullptr)
 5         return result;
 6 
 7     TreeNode *pCur, *pLastVisit;
 8     pCur = root;
 9     pLastVisit = nullptr;
10 
11     while (pCur) {          // 把 pCur 移动到最左下方
12         stk.push(pCur);
13         pCur = pCur->left;   
14     }
15     while (!stk.empty()) {
16         pCur = stk.top();
17         stk.pop();
18         if (pCur->right == nullptr || pCur->right == pLastVisit) {  // 如果当前节点无右子树或者右子树已经被访问过，则访问
19             result.push_back(pCur->val);
20             cout << ‘\t‘ << pCur->val;
21             pLastVisit = pCur;
22         }
23         else {  // 跳到右子树去
24             stk.push(pCur);  // 根节点再次入栈
25             pCur = pCur->right;
26             while (pCur) {
27                 stk.push(pCur);
28                 pCur = pCur->left;
29             }
30         }
31     }
32     cout << endl;
33     return result;
34 }

 1 void levelOrderI(TreeNode* root) {  // 层次遍历,不分层次
 2     if (root == nullptr)
 3         return;
 4     queue<TreeNode*> q;
 5     q.push(root);
 6     while (!q.empty()) {
 7         TreeNode *temp = q.front();
 8         q.pop();
 9         cout << temp->val << ‘\t‘;
10         if (temp->left)
11             q.push(temp->left);
12         if (temp->right)
13             q.push(temp->right);
14     }
15     cout << endl;
16 }

 1 vector<vector<int>> levelOrderII1(TreeNode* root) { // 迭代版
 2     vector<vector<int>> result;
 3     queue<TreeNode*> current, next;
 4 
 5     if (root == nullptr)
 6         return result;
 7     else
 8         current.push(root);
 9 
10     while (!current.empty()) {
11         vector<int> level;  // elements in one level
12         while (!current.empty()) {
13             TreeNode *node = current.front();
14             current.pop();
15             level.push_back(node->val);
16             if (node->left)
17                 next.push(node->left);
18             if (node->right)
19                 next.push(node->right);
20         }
21         result.push_back(level);
22         swap(current, next);
23     }
24     return result;
25 }
26 
27 
28 void traverse(TreeNode *root, size_t level, vector<vector<int>>& result) {
29     if (!root)
30         return;
31     if (level > result.size())
32         result.push_back(vector<int>());  // 如果层数不够，新加一层来存储
33 
34     result[level - 1].push_back(root->val);
35     traverse(root->left, level + 1, result);
36     traverse(root->right, level + 1, result);
37 }
38 vector<vector<int>> levelOrderII2(TreeNode* root) {   // 递归版
39     vector<vector<int>> result;
40     traverse(root, 1, result);
41     return result;
42 }

 1 vector<vector<int>> levelOrderBottomI(TreeNode *root) {  // 递归版
 2     vector<vector<int>> result;
 3     traverse(root, 1, result);
 4     reverse(result.begin(), result.end());   // 多了这一行，调用相同的函数
 5     return result;
 6 }
 7 
 8 vector<vector<int>> levelOrderBottomII(TreeNode *root) {
 9     vector<vector<int>> result;
10     if (root == nullptr)
11         return result;
12 
13     queue<TreeNode*> current, next;
14 
15     current.push(root);
16     while (!current.empty()) {
17         vector<int> level;  // elments in one level
18         while (!current.empty()) {
19             TreeNode *node = current.front();
20             current.pop();
21             level.push_back(node->val);
22             if (node->left)
23                 next.push(node->left);
24             if (node->right)
25                 next.push(node->right);
26         }
27         result.push_back(level);
28         swap(next, current);
29     }
30     reverse(result.begin(), result.end());  // 多了这一行
31     return result;
32 }

 1 void traverse(TreeNode *root, size_t level, vector <vector<int>>& result, bool left_to_right) {  // 递归往返方向
 2     if (!root)
 3         return;
 4 
 5     if (level > result.size())
 6         result.push_back(vector<int>());
 7 
 8     if (left_to_right)
 9         result[level - 1].push_back(root->val);
10     else
11         result[level - 1].insert(result[level].begin(), root->val);
12 
13     traverse(root->left, level + 1, result, !left_to_right);
14     traverse(root->right, level + 1, result, !left_to_right);
15 }
16 vector<vector<int>> zigzagLevelOrderI(TreeNode *root) {
17     vector<vector<int>> result;
18     traverse(root, 1, result, true);
19     return result;
20 }
21 
22 
23 vector<vector<int>> zigzagLevelOrderII(TreeNode *root) {  // 迭代版
24     vector<vector<int>> result;
25     queue<TreeNode*> current, next;
26     bool left_to_right = true;
27 
28     if (root == nullptr)
29         return result;
30     else
31         current.push(root);
32 
33     while (!current.empty()) {
34         vector<int> level;     // elements in one level
35         while (!current.empty()) {
36             TreeNode *node = current.front();
37             current.pop();
38             level.push_back(node->val);
39             if (node->left)
40                 next.push(node->left);
41             if (node->right)
42                 next.push(node->right);
43         }
44         if (!left_to_right)                       // 多加了这一行
45             reverse(level.begin(),level.end());
46         result.push_back(level);
47         left_to_right = !left_to_right;
48         swap(next, current);
49     }
50     return result;
51 }

 1 bool isSameTreeI(TreeNode *p, TreeNode *q) {  // 递归版
 2     if (!p && !q)
 3         return true;
 4     if (!p || !q)
 5         return false;
 6 
 7     return p->val == q->val && isSameTreeI(p->left, q->left) && isSameTreeI(p->right, q->right);
 8 }
 9 
10 bool isSampleTreeII(TreeNode *p, TreeNode *q) {  // 迭代
11     stack<TreeNode*> stk;
12     stk.push(p);
13     stk.push(q);
14 
15     while (!stk.empty()) {
16         p = stk.top();
17         stk.pop();
18         q = stk.top();
19         stk.pop();
20         
21         if (!q && !q)
22             continue;
23         if (!q || !p)
24             return false;
25         if (q->val != p->val)
26             return false;
27 
28         stk.push(p->right);
29         stk.push(q->right);
30 
31         stk.push(p->left);
32         stk.push(q->left);
33     }
34     return true;
35 }

 1 bool isSymmetricI(TreeNode *p, TreeNode *q) {  // 迭代版本
 2     if (!p && !q)
 3         return true;
 4     if (!p || !q)
 5         return false;
 6     return p->val == q->val && isSymmetricI(p->left, q->left) && isSymmetricI(p->right, q->left);
 7 }
 8 bool isSymmetricI(TreeNode *root) {
 9     if (root == nullptr) return true;
10     return isSymmetricI(root->left, root->right);
11 }
12 
13 
14 bool isSymmetricII(TreeNode *root) {  // 迭代版
15     if (!root) return true;
16     stack<TreeNode*> stk;
17     stk.push(root->left);
18     stk.push(root->right);
19 
20     while (!stk.empty()) {
21         auto p = stk.top();
22         stk.pop();
23         auto q = stk.top();
24         stk.pop();
25 
26         if (!p && !p) continue;
27         if (!p || !q) return false;
28         if (p->val != q->val) return false;
29 
30         stk.push(p->left);
31         stk.push(q->right);
32 
33         stk.push(p->right);
34         stk.push(q->left);
35     }
36     return true;
37 }

 1 int balancedHeight(TreeNode *root) {
 2     if (root == nullptr)
 3         return 0;   // 终止条件
 4 
 5     int leftHeight = balancedHeight(root->left);
 6     int rightHeight = balancedHeight(root->right);
 7 
 8     if (leftHeight < 0 || rightHeight < 0 || abs(leftHeight - rightHeight) > 1)   // 什么时候 leftHight 会小于 0？
 9         return -1;   // 剪枝
10 
11     return max(leftHeight, rightHeight) + 1;
12 
13 }
14 bool isBalanceTree(TreeNode *root) {
15     return balancedHeight(root) >= 0;
16 }

 1 void flatten(TreeNode *root) {  // 迭代版，先序遍历然后组成单链表形状
 2     if (root == nullptr)
 3         return;
 4     stack<TreeNode*> stk;
 5     stk.push(root);
 6     TreeNode dummy(-1);
 7     TreeNode *prev = &dummy;
 8 
 9     while (!stk.empty()) {
10         TreeNode *node = stk.top();
11         stk.pop();
12 
13         if (node->right)
14             stk.push(node->right);
15         if (node->left)
16             stk.push(node->left);
17 
18         node->left = nullptr;
19         prev->right = node;
20         prev = prev->right;
21     }
22     root = dummy.right;
23 }

 1 void connectI(TreeLinkNode *root) {  // 迭代版
 2     while (root) {
 3         TreeLinkNode *next = nullptr;  // the first node of next level
 4         TreeLinkNode *prev = nullptr; //   previous node on the same level
 5         while (root) {  // 对于每一行来说
 6             if (!next)
 7                 next = root->left ? root->left : root->right;
 8 
 9             if (root->left) {
10                 if (prev)
11                     prev->next = root->left;
12                 prev = root->left;
13             }
14             if (root->right) {
15                 if (prev)
16                     prev->next = root->right;
17                 prev = root->right;
18             }
19         }
20         root = next;   // turn to next level
21     }
22 }
23 
24 
25 void connectII(TreeLinkNode *root) {  // 迭代版
26     if (root == nullptr) return;
27 
28     TreeLinkNode dummy(-1);
29     for (TreeLinkNode *curr = root, *prev = &dummy; curr; curr = curr->next) {
30         if (curr->left) {
31             prev->next = curr->left;
32             prev = prev->next;
33         }
34         if (curr->right) {
35             prev->next = curr->right;
36             prev = prev->next;
37         }
38     }
39     connectII(dummy.next);   // 下一层的第一个节点
40 }

 1 TreeNode* buildTreeI(vector<int>::iterator pre_first, vector<int>::iterator pre_last,
 2     vector<int>::iterator in_first, vector<int>::iterator in_last) {
 3     if (pre_first == pre_last)  // 如果 左子树为空，结束
 4         return nullptr;
 5     if (in_first == in_last)    // 如果 右子树为空，结束
 6         return nullptr;
 7 
 8     auto root = new TreeNode(*pre_first);
 9     auto inRootPos = find(in_first, in_last, *pre_first);
10     int leftSize = distance(in_first, inRootPos);
11 
12     root->left = buildTreeI(next(pre_first), next(pre_first, leftSize + 1),in_first,next(in_first,leftSize));
13     root->right = buildTreeI(next(pre_first, leftSize + 1), pre_last, next(inRootPos), in_last);
14 
15     return root;
16 }
17 TreeNode* buildTreeI(vector<int>& preOrder, vector<int>& inOrder) {  // 根据先序遍历和中序遍历序列构造二叉树
18     return buildTreeI(begin(preOrder), end(preOrder), begin(inOrder), end(inOrder));
19 }

 1 TreeNode* buildTreeII(vector<int>::iterator in_first, vector<int>::iterator in_last,
 2     vector<int>::iterator post_first, vector<int>::iterator post_last) {
 3 
 4     if (in_first == in_last)
 5         return nullptr;
 6     if (post_first == post_last)
 7         return nullptr;
 8 
 9     int pRootValue = *prev(post_last);
10     TreeNode* root = new TreeNode(pRootValue);
11 
12     auto inRootPos = find(in_first, in_last, pRootValue);
13     int leftSize = distance(in_first, inRootPos);
14 
15     root->left = buildTreeII(in_first, inRootPos, post_first, next(post_first, leftSize));  // 注意迭代器“前闭后开”原则
16     root->right = buildTreeII(next(inRootPos), in_last, next(post_first, leftSize), prev(post_last));
17 
18     return root;
19 }
20 TreeNode* buildTreeII(vector<int>& inOrder, vector<int>& postOrder) {
21     return buildTreeII(begin(inOrder), end(inOrder), begin(postOrder), end(postOrder));
22 }

 1 int numTrees(int n) {  // 一维动态规划
 2     vector<int> f(n + 1, 0);
 3 
 4     f[0] = 1;
 5     f[1] = 1;
 6     for (int i = 2; i <= n; ++i) {
 7         for (int k = 1; k <= i; ++k)
 8             f[i] += f[k - 1] * f[i - k];
 9     }
10     return f[n];
11 }