二叉树总结
1
2
3
4
5
6
| struct TreeNode{
int value;
TreeNode *left;
TreeNode *right
TreeNode(int v): value(v),left(nullptr), right(nullptr) {}
};
|
遍历二叉树
前序遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution{
public:
vector<int>preOrderTraversal(TreeNode* tree) {
vector<int> ans;
function<void(TreeNode *)> preOrderTraversalHelper = [&](TreeNode *node){
if (!node) return;
ans.push_back(node->val);
preOrderTraversalHelper(node->left);
preOrderTraversalHelper(node->right)
};
preOrderTraversalHelper(tree);
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution{
public:
vector<int>preOrderTraversal(TreeNode *node){
if (!node) return {};
vector<int> ans;
stack<TreeNode *> stk_;
stk_.push(node);
while (!stk_.empty()) {
TreeNode *root = stk_.top();
stk_.pop();
ans.(root->value);
if (root->right)
stk_.push(root->right);
if (root->left)
stk_.push(root->left);
}
return ans;
}push_back
};
|
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
| class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> nums;
TreeNode* cur = nullptr;
while (root) {
if (root->right) {
cur = root->right;
while (cur->left && cur->left != root) {
cur = cur->left;
}
if (cur->left == root) {
cur->left = nullptr;
root = root->left;
} else {
nums.push_back(root->val);
cur->left = root;
root = root->right;
}
} else {
nums.push_back(root->val);
root = root->left;
}
}
return nums;
}
}
|
中序遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public:
vector<int> inOrderTraversal(TreeNode *node) {
vector<int> ans;
function<void(TreeNode *)> inOrderTraversalHelper = [&](TreeNode * root){
if (!root) return;
inOrderTraversalHelper(root->left)
ans.push_back(root->val);
inOrderTraversalHelper(root->right);
};
inOrderTraversalHelper(root);
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution{
public:
vector<int>inOrderTraversal(TreeNode *root){
if (!root) return {};
vector<int> ans;
stack<TreeNode *> stk_;
while (root || !stk_.empty()) {
while (root) {
stk_.push(root);
root = root->left;
}
root = stk_.top(); stk_.pop();
ans.push_back(root->value);
root = root->right;
}
return ans;
}
};
|
后序遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public:
vector<int> postOrderTraversal(TreeNode *node) {
vector<int> ans;
function<void(TreeNode *)>postOrderTraversalHelper = [&](TreeNode *root){
if (!root) return;
postOrderTraversal(root->left);
postOrderTraversal(root->right);
ans.push_back(root);
};
postOrderTraversal(node);
return ans;
}
};
|
- 非递归
two stack
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public:
vector<int> postOrderTraversal(TreeNode *root){
if (!root) return {};
stack<TreeNode *> stk_, _stk;
stk_.push(root);
TreeNode *node = nullptr;
while (!stk_.empty()) {
node = stk_.top();stk_.pop();
_stk.push(node);
if (node->left)
stk_.push(node->left);
if (node->right)
stk_.push(node->right);
}
while (!_stk.empty()) {
ans.push_back(_stk.top());
_stk.pop();
}
}
};
|
one stack, 需要记录上一个输出的节点的指针，
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
| class Solution {
public:
vector<int> postOrderTraversal(TreeNode *root) {
if (!root) return {};
vector<int> ans;
stack<TreeNode *>stk_;
TreeNode *last = nullptr;
while (root || !stk_.empty()) {
if (root) {
stk_.push(root);
root = root->left;
} else {
TreeNode *node = stk_.top();
if (node->right && last != node->right) {
root = node->right;
} else {
ans.push_back(node->value);
last = node;
stk_.pop();
}
}
}
return ans;
}
};
|
Morris Traversal O(n) time O(1) space
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
44
45
46
47
48
49
50
51
52
53
54
55
| class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> nodes;
TreeNode* dummy = new TreeNode(0);
dummy -> left = root;
TreeNode* cur = dummy;
while (cur) {
if (cur -> left) {
TreeNode* pre = cur -> left;
while (pre -> right && (pre -> right != cur)) {
pre = pre -> right;
}
if (!(pre -> right)) {
pre -> right = cur;
cur = cur -> left;
} else {
reverseAddNodes(cur -> left, pre, nodes);
pre -> right = NULL;
cur = cur -> right;
}
} else {
cur = cur -> right;
}
}
return nodes;
}
private:
void reverseNodes(TreeNode* start, TreeNode* end) {
if (start == end) {
return;
}
TreeNode* x = start;
TreeNode* y = start -> right;
TreeNode* z;
while (x != end) {
z = y -> right;
y -> right = x;
x = y;
y = z;
}
}
void reverseAddNodes(TreeNode* start, TreeNode* end, vector<int>& nodes) {
reverseNodes(start, end);
TreeNode* node = end;
while (true) {
nodes.push_back(node -> val);
if (node == start) {
break;
}
node = node -> right;
}
reverseNodes(end, start);
}
};
|
