二叉树相关知识点总结

二叉树的定义

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

二叉树的遍历

遍历中的“前”、“中”、“后”序指的是访问根节点是在访问孩子节点之前、之中还是之后。

前序遍历

题目链接:https://leetcode-cn.com/problems/binary-tree-preorder-traversal/

递归解法

在所有遍历的递归解法中,需要注意的只有当遇到节点为空的时候需要 return 就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
private:
vector<int> result;

void doTraversal(TreeNode* t) {
if (t == nullptr) {
return;
}

this->result.push_back(t->val);
doTraversal(t->left);
doTraversal(t->right);
}
public:
vector<int> preorderTraversal(TreeNode* root) {
doTraversal(root);

return this->result;
}
};

迭代解法1

使用一个栈作为辅助,如果有左孩子,不断访问左孩子并将其进栈,然后再去考虑右孩子。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> result;

if (root == nullptr) return result;

stack<TreeNode*> s;
TreeNode* t = root;

while (!s.empty() || t != nullptr) {
while(t != nullptr) {
result.push_back(t->val);
s.push(t);
t = t->left;
}
t = s.top();
s.pop();
t = t->right;
}

return result;
}
};

迭代解法2

使用一个辅助栈,先访问当前根节点,因为栈是后进先出,所以然后先将右孩子进栈,再将左孩子进栈。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> result;

if (root == nullptr) return result;

stack<TreeNode*> s;
TreeNode* t;

s.push(root);
while (!s.empty()) {
t = s.top();
s.pop();
result.push_back(t->val);
if (t->right != nullptr) s.push(t->right);
if (t->left != nullptr) s.push(t->left);
}

return result;
}
};

中序遍历

题目链接:https://leetcode-cn.com/problems/binary-tree-inorder-traversal/

递归解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
private:
vector<int> result;

void doTraversal(TreeNode* t) {
if (t == nullptr) return;
doTraversal(t->left);
this->result.push_back(t->val);
doTraversal(t->right);
}
public:
vector<int> inorderTraversal(TreeNode* root) {
doTraversal(root);

return result;
}
};

迭代解法1

和前序遍历的迭代解法 1 类似,只是访问根节点的实际从将左孩子压入栈变成了在出栈的时候。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> result;
if (root == nullptr) return result;

stack<TreeNode*> s;
TreeNode* t = root;

while (!s.empty() || t != nullptr ) {
while(t != nullptr) {
s.push(t);
t = t->left;
}
t = s.top();
result.push_back(t->val);
s.pop();
t = t->right;
}

return result;
}
};

迭代解法2

还有一种只是用一层循环的解法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> result;
if (root == nullptr) return result;

stack<TreeNode*> s;
TreeNode* t = root;

while (!s.empty() || t != nullptr ) {
if (t != nullptr) {
s.push(t);
t = t->left;
} else {
t = s.top();
result.push_back(t->val);
s.pop();
t = t->right;
}
}

return result;
}
};

后序遍历

题目链接:https://leetcode-cn.com/problems/binary-tree-postorder-traversal

递归解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
private:
vector<int> result;

void doTraversal(TreeNode* t) {
if (t == nullptr) return;
doTraversal(t->left);
doTraversal(t->right);
this->result.push_back(t->val);
}
public:
vector<int> postorderTraversal(TreeNode* root) {
doTraversal(root);

return this->result;
}
};

迭代解法1

思路为拆解并用栈模拟递归,但是一个栈不足以保存递归的所有信息,所以用了两个栈

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
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> result;
if (root == nullptr) return result;

stack<TreeNode*> s, h;
TreeNode* t = root;

while (!s.empty() || t != nullptr) {
if (t != nullptr) {
s.push(t);
t = t->left;
} else {
t = s.top();
if (!h.empty() && t == h.top()) {
result.push_back(t->val);
h.pop();
s.pop();
t = nullptr;
} else if (t->right != nullptr) {
h.push(t);
t = t->right;
} else {
result.push_back(t->val);
s.pop();
t = nullptr;
}
}
}

return result;
}
};

迭代解法2

后序遍历需要使用双栈法,使用第一个栈做类似前序遍历的操作(只是这里访问左孩子需要在右孩子之前),使用第二个栈将前序遍历的操作进行逆序。最后将第二个栈的内容输出。

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> result;
if (root == nullptr) return result;

stack<TreeNode*> s;
stack<int> h;
TreeNode* t;

s.push(root);
while (!s.empty()) {
t = s.top();
s.pop();
h.push(t->val);

if (t->left != nullptr) s.push(t->left);
if (t->right != nullptr) s.push(t->right);
}

while (!h.empty()) {
result.push_back(h.top());
h.pop();
}

return result;
}
};

层序遍历

题目链接:https://leetcode-cn.com/problems/binary-tree-level-order-traversal/

使用队列进行按照从上到下从左到右的顺序进行迭代,每访问到一个节点就去将它的左右孩子加入队列之中。

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
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> result;
if (root == nullptr) return result;

int this_level_count = 1;
int next_level_count = 0;
queue<TreeNode*> q;
TreeNode* t;

q.push(root);
result.push_back(vector<int>());
while (!q.empty()) {
t = q.front();
q.pop();
result.back().push_back(t->val);
if (t->left != nullptr) {
q.push(t->left);
next_level_count++;
}
if (t->right != nullptr) {
q.push(t->right);
next_level_count++;
}

if (--this_level_count == 0) {
this_level_count = next_level_count;
next_level_count = 0;
if (!q.empty()) result.push_back(vector<int>());
}
}

return result;
}
};

二叉树的重建

从前序遍历和中序遍历恢复二叉树

题目链接:https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

递归解法

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
class Solution {
private:
TreeNode* build(
vector<int>& preorder,
vector<int>& inorder,
int pre_start,
int pre_end,
int in_start,
int in_end
) {
if (pre_start > pre_end || in_start > in_end) return nullptr;

TreeNode* root = new TreeNode(preorder[pre_start]);
if (pre_start == pre_end) return root;

int left_num = 0;
while (preorder[pre_start] != inorder[in_start + left_num]) left_num++;

root->left = build(
preorder,
inorder,
pre_start + 1,
pre_start + left_num,
in_start,
in_start + left_num - 1
);
root->right = build(
preorder,
inorder,
pre_start + left_num + 1,
pre_end,
in_start + left_num + 1,
in_end
);

return root;
}
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
if(preorder.size() == 0) return nullptr;

return build(preorder, inorder, 0, preorder.size() - 1, 0, inorder.size() - 1);
}
};

从前序遍历和后续遍历恢复二叉树

题目链接:https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/

递归解法

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 {
TreeNode* build(
vector<int>& inorder,
vector<int>& postorder,
int in_start,
int in_end,
int post_start,
int post_end
) {
if (in_start > in_end || post_start > post_end) return nullptr;

TreeNode* root = new TreeNode(postorder[post_end]);
if (in_start == in_end) return root;

int right_num = 0;
while (postorder[post_end] != inorder[in_end - right_num]) right_num++;

root->left = build(
inorder,
postorder,
in_start,
in_end - right_num - 1,
post_start,
post_end - right_num - 1
);
root->right = build(
inorder,
postorder,
in_end - right_num + 1,
in_end,
post_end - right_num,
post_end - 1
);

return root;
}
public:
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
if (inorder.size() == 0) return nullptr;

return build(inorder, postorder, 0, inorder.size() - 1, 0, postorder.size() - 1);
}
};