【道德经·第二章】天下皆知美之为美，斯恶（è）已；皆知善之为善，斯不善已。故有无相生，难易相成，长短相较，高下相倾，音声相和（hè），前后相随。
前序遍历
递归遍历方法
1
2
3
4
5
6
7
8
| void PreOrder(TreeNode* node) {
if(node == nullptr)
return;
printf("%d ", node->val);
PreOrder(node->left);
PreOrder(node->right);
}
|
非递归遍历方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| void PreOrder(TreeNode* node) {
if(node == nullptr)
return;
stack<TreeNode*> stk;
stk.push(root);
while(!stk.empty()) {
node *p = stk.top(); stk.pop();
printf("%d ", p->val);
if(p->right)
stk.push(p->right);
if(p->left)
stk.push(p->left);
}
}
|
中序遍历
递归遍历方法
1
2
3
4
5
6
7
8
| void InOrder(TreeNode* node) {
if(node == nullptr)
return;
InOrder(node->left);
printf("%d ", node->val);
InOrder(node->right);
}
|
非递归遍历方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| void InOrder(TreeNode* node) {
if(node == nullptr)
return;
stack<TreeNode*> stk;
TreeNode *p = node;
while(p || !stk.empty()) {
if(p) {
stk.push(p);
p = p->left;
} else {
TreeNode *p = stk.top();
stk.pop();
printf("%d", p->val);
p = p->right;
}
}
}
|
后序遍历
递归遍历方法
1
2
3
4
5
6
7
8
| void PostOrder(TreeNode* node) {
if(node == nullptr)
return;
PostOrder(node->left);
PostOrder(node->right);
printf("%d ", node->val);
}
|
非递归遍历方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| void PostOrder(TreeNode* node) {
if(node == nullptr)
return;
stack<TreeNode*> stk1, stk2;
stk1.push(node);
while(!stk1.empty()) {
TreeNode *p = stk1.top();
stk1.pop();
stk2.push(p);
if(p->left)
stk1.push(p->left);
if(p->right)
stk1.push(p->right);
}
while(!stk2.empty()) {
TreeNode *p = stk2.top();
stk2.pop();
printf("%d ", p->val);
}
}
|
层序遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| void LevelOrder(TreeNode* root) {
queue<TreeNode*> q;
q.push(root);
while(!q.empty()) {
TreeNode *p = q.front();
q.pop();
printf("%d ", p->val);
if(p->left)
q.push(p->left);
if(p->right)
q.push(p->right);
}
}
|
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
| vector<vector<int>> levelOrderBottom(TreeNode* root) {
vector<vector<int>> v;
stack<vector<int>> stk;
if(root == NULL) return v;
queue<TreeNode*> q;
q.push(root);
while(!q.empty()) {
int cnt = q.size();
vector<int> v1;
while(cnt--) {
TreeNode* tmp = q.front();
q.pop();
v1.push_back(tmp->val);
if(tmp->left) q.push(tmp->left);
if(tmp->right) q.push(tmp->right);
}
stk.push(v1);
}
while(!stk.empty()) {
v.emplace_back(stk.top());
stk.pop();
}
return v;
}
|
给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| vector<int> rightSideView(TreeNode* root) {
vector<int> res;
if(!root) return res;
queue<TreeNode*> q;
q.push(root);
while(!q.empty()) {
int sz = q.size();
for(int i = 1; i <= sz; i++) {
TreeNode *t = q.front(); q.pop();
if(i == sz) res.push_back(t->val);
if(t->left) q.push(t->left);
if(t->right) q.push(t->right);
}
}
return res;
}
|
给你二叉树的根节点 root ，返回其节点值的 锯齿形层序遍历 。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
解法一（栈）
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
| vector<vector<int> > Print(TreeNode* pRoot) {
if(pRoot == nullptr) return{};
vector<vector<int> > res;
vector<int> out;
stack<TreeNode*> stk[2];
int cur = 0;
int nxt = 1;
stk[cur].push(pRoot);
while(!stk[0].empty() || !stk[1].empty()) {
TreeNode *t = stk[cur].top(); stk[cur].pop();
out.push_back(t->val);
if(cur == 0) {
if(t->left) stk[nxt].push(t->left);
if(t->right) stk[nxt].push(t->right);
} else {
if(t->right) stk[nxt].push(t->right);
if(t->left) stk[nxt].push(t->left);
}
if(stk[cur].empty()) {
cur = 1-cur;
nxt = 1-nxt;
res.push_back(out);
out.clear();
}
}
return res;
}
|
解法二（deque）
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
|
class Solution {
public:
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
if(!root) return {};
vector<vector<int> > res;
vector<int> out;
queue<TreeNode*> q;
q.push(root);
int step = 1;
while(!q.empty()) {
deque<int> dq;
int n = q.size();
for(int i = 0; i < n; i++) {
TreeNode *t = q.front(); q.pop();
if(step%2 == 1) {
dq.push_back(t->val);
} else {
dq.push_front(t->val);
}
if(t->left) q.push(t->left);
if(t->right) q.push(t->right);
}
res.push_back(vector<int>{dq.begin(), dq.end()});
step++;
}
return res;
}
};
|
给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
1
2
3
4
5
6
7
8
| bool isSameTree(TreeNode* p, TreeNode* q) {
if(p==nullptr && q==nullptr)
return true;
if(!p || !q) return false;
return (p->val==q->val) && isSameTree(p->left, q->left) &&
isSameTree(p->right, q->right);
}
|
给你一个二叉树的根节点 root ， 检查它是否轴对称。
1
2
3
4
5
6
7
8
9
10
11
| bool isSymmetric(TreeNode* root) {
if(root == NULL) return true;
return isSymmetric(root->left, root->right);
}
bool isSymmetric(TreeNode* left, TreeNode* right) {
if(!left && !right) return true;
if(!left || !right) return false;
if(left->val != right->val) return false;
return isSymmetric(left->left, right->right) && isSymmetric(left->right, right->left);
}
|
给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
1
2
3
4
5
6
7
8
9
10
11
| TreeNode* invertTree(TreeNode* root) {
if(!root) return nullptr;
TreeNode *left = invertTree(root->left);
TreeNode *right = invertTree(root->right);
root->left = right;
root->right = left;
return root;
}
|
给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
1
2
3
4
5
6
7
8
| int maxDepth(TreeNode* root) {
if(!root) return 0;
int l = maxDepth(root->left);
int r = maxDepth(root->right);
return l>r ? l+1 : r+1;
}
|
给定一个二叉树，判断它是否是高度平衡的二叉树。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| bool IsBalanced_Solution(TreeNode* pRoot) {
return depth(pRoot) != -1;
}
int depth(TreeNode* node) {
if(node == nullptr) {
return 0;
}
int ldep = depth(node->left);
if(ldep == -1) return -1;
int rdep = depth(node->right);
if(rdep == -1) return -1;
int diff = abs(ldep - rdep);
if(diff > 1) return -1;
return max(ldep, rdep) + 1;
}
|
给定一个二叉树的 root ，确定它是否是一个 完全二叉树 。在一个 完全二叉树 中，除了最后一个关卡外，所有关卡都是完全被填满的，并且最后一个关卡中的所有节点都是尽可能靠左的。它可以包含 1 到 2h 节点之间的最后一级 h 。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| bool isCompleteTree(TreeNode* root) {
if(!root) return false;
queue<TreeNode*> q;
q.push(root);
while(!q.empty()) {
TreeNode *t = q.front(); q.pop();
if(!t) {
while(!q.empty()) {
TreeNode *t1 = q.front(); q.pop();
if(t1) return false;
}
}
if(t) q.push(t->left);
if(t) q.push(t->right);
}
return true;
}
|
给你两棵二叉树： root1 和 root2 。想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
if(t1==nullptr && t2==nullptr)
return nullptr;
if(t1==nullptr) return t2;
if(t2==nullptr) return t1;
TreeNode *root = new TreeNode(t1->val + t2->val);
root->left = mergeTrees(t1->left, t2->left);
root->right = mergeTrees(t1->right, t2->right);
return root;
}
|
位我上者，灿烂星空；道德律令，在我心中。