最近刷算法，补充算算法知识，因为本人的基础薄弱，补起来比较吃力。二叉树的遍历方法，非递归版本的遍历方法让我迷惑，但是我读到了一篇写的非常精彩的文章 https://zhuanlan.zhihu.com/p/30490183 ；有兴趣的可以去参考下原文。
我在这里总结出核心思想。
对于二叉树中的任何一个节点而言，它都有两个角色需要扮演，一个是作为值存储的角色（角色1），另一个角色是作为它所带领的子树的一个代表（角色2）。而我们设置的boolean变量，就是为了说明我当前拿到的这个节点，应该是以一个值存储的这种角色对待它(True)，还是应该以一个子树的代表这种角色对待它（False），如果是前者，那么就简单的将其所存储的值打印出来，如果是后者，我们需要继续探索由它带领的子树。
通过这个核心思想，我们可以将二叉数的遍历方法做一个统一的规划了，我们先包装Node,让他带一个是否访问过的标志，(如果你不用Java,比如py,你可以直接用元组)。
`
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
|
class Solution {
class TreeNodeWhithBoolean {
TreeNode node;
boolean visited;
public TreeNodeWhithBoolean(TreeNode node,boolean visited){
this.node = node;
this.visited = visited;
}
}
public List<Integer> preorderTraversal(TreeNode root) {
if(root == null){
return new ArrayList();
}
List<Integer> list = new ArrayList<Integer>();
TreeNodeWhithBoolean rootBoolean = new TreeNodeWhithBoolean(root, false);
Stack<TreeNodeWhithBoolean> stack = new Stack<TreeNodeWhithBoolean>();
stack.push(rootBoolean);
while(!stack.isEmpty()){
TreeNodeWhithBoolean current = stack.pop();
if(current.visited){
list.add(current.node.val);
}else {
if(current.node.right != null){
stack.push(new TreeNodeWhithBoolean(current.node.right, false));
}
if(current.node.left != null){
stack.push(new TreeNodeWhithBoolean(current.node.left, false));
}
stack.push(new TreeNodeWhithBoolean(current.node, true));
}
}
return list;
}
}
|
上面这段是前序遍历的代码，中序遍历和后续遍历的代码也大同小异，只需要替换入栈顺序即可，因为栈为我们提供了一个天然翻转的工具。 比如前序遍历的顺序是 根，左，右。也就是说出栈顺序就是这个，那入栈顺序反过来就好了。其他的遍历也是完全按照这个思路来。