在此感谢 leetcode 网友提供的遍历方法

https://leetcode-cn.com/problems/binary-tree-inorder-traversal/solution/yan-se-biao-ji-fa-yi-chong-tong-yong-qie-jian-ming/

二叉树的遍历是老生常谈的话题,递归方法最容易理解,但空间复杂度极高,由此衍生出了迭代遍历,但思维量巨大,每种遍历都需要写不同风格的代码。

我最近重写遍历时发现 网友 独创的遍历方式。

采用颜色标记法,未访问的用白色标记,访问的用黑色标记。

我们针对不同的遍历,只需要修改添加到数组时的顺序即可。

三种遍历方式代码风格极其相似,你还会怕写不出迭代遍历的代码吗?

前序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
var preorderTraversal = function(root) {
let white = 0, black = 1
let stack = [[white, root]]
let result = []
while(stack.length > 0) {
let [color, node] = stack.pop()
if(!node) continue
if (color == white) {
stack.push([white, node.right])
stack.push([white, node.left])
stack.push([black, node])
}else{
result.push(node.val)
}
}
return result
};

中序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
var inorderTraversal = function(root) {
let white = 0, black = 1
let stack = [[white, root]]
let result = []
while(stack.length > 0) {
let [color , node] = stack.pop()
if (!node) {
continue
}
if(color == white) {
stack.push([white, node.right])
stack.push([black, node])
stack.push([white, node.left])
}else{
result.push(node.val)
}
}
return result
};

后序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
var postorderTraversal = function(root) {
let white = 0, black = 1
let stack = [[white, root]]
let result = []
while(stack.length > 0) {
let [color,node] = stack.pop()

if (!node) continue
if (color == white) {
stack.push([black,node])
stack.push([white, node.right])
stack.push([white, node.left])
}else {
result.push(node.val)
}
}
return result
};