二叉树的非递归遍历你会吗?-一种格式搞定三种遍历

一个格式搞定三种遍历

二叉树的前、中、后序遍历的递归写法非常好写,我们常用的也是递归写法。但如果要使用迭代的方式写出这三种遍历的话,可能就没那么简单了。

前序和中序比较简单,使用栈存储访问过的节点,再注意一下访问的次序即可。但后序遍历就不那么好写了,今天在做题的时候,发现了一套统一的写法,简洁、大方又对称。这里分享给大家。

前序遍历

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
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> result;
stack<TreeNode*> node_stack;
if (root != nullptr) {
node_stack.push(root);
}
while (!node_stack.empty()) {
auto node = node_stack.top();
node_stack.pop();
if (node != nullptr) {
// 这块的顺序决定了遍历的顺序
if (node->right) node_stack.push(node->right);
if (node->left) node_stack.push(node->left);
node_stack.push(node);
node_stack.push(nullptr);
} else {
auto top = node_stack.top();
result.push_back(top->val);
node_stack.pop();
}
}

return result;
}
};

中序遍历

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> inorderTraversal(TreeNode* root) {
vector<int> result;
stack<TreeNode*> node_stack;
if (root != nullptr) {
node_stack.push(root);
}

while (!node_stack.empty()) {
auto node = node_stack.top();
node_stack.pop();
if (node != nullptr) {
// 右->根->左
if (node->right) node_stack.push(node->right);
node_stack.push(node);
node_stack.push(nullptr);
if (node->left) node_stack.push(node->left);
} else {
auto top = node_stack.top();
result.push_back(top->val);
node_stack.pop();
}
}

return result;
}
};

后序遍历

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
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> result;
stack<TreeNode*> node_stack;
if (root != nullptr) {
node_stack.push(root);
}

while (!node_stack.empty()) {
auto node = node_stack.top();
node_stack.pop();

if (node != nullptr) {
// 根->右->左
node_stack.push(node);
node_stack.push(nullptr);
if (node->right) node_stack.push(node->right);
if (node->left) node_stack.push(node->left);
} else {
auto top = node_stack.top();
node_stack.pop();
result.push_back(top->val);
}
}

return result;
}
};

总结

在代码中,使用nullptr来标注接下来的结点是否要被访问(处理)。三种遍历的不同之处在于代码中有注释的地方,不同的遍历方式只需要调整入栈的顺序即可。

强烈推荐::fire:。