记录生活中的点点滴滴

0%

二叉树的非递归遍历

昨天刷题后序遍历有点懵,得,今天再记录一下二叉树的非递归前序、后序、中序遍历。

以下面的二叉树为例:

前序遍历

前序遍历:顺序是 左节点-》根节点-》右节点

即:[1,2,4,8,9,5,3,6,7]

借助栈,首先根节点入栈,然后进入循环:出栈,入栈左右节点。退出条件为栈为空。

思想还是比较简单的,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
if(root==null)return res;
//借助栈进行遍历
Stack<TreeNode> s = new Stack<>();
s.push(root);
while(!s.isEmpty()){
TreeNode t = s.pop();
res.add(t.val);
if(t.right!=null){
s.push(t.right);
}
if(t.left!=null){
s.push(t.left);
}
}
return res;
}

结果如下:

后序遍历

后序遍历:顺序是 左节点-》右节点-》根节点

即:[8,9,4,5,2,6,7,3,1]

怎么做呢?其实我们换一种思想,先看看它的镜像二叉树的前序遍历:

即:[1,3,7,6,2,5,4,9,8]

发现了吧,它的镜像二叉树的前序遍历的结果,再倒置一下就是我们要的这个二叉树的后序遍历了!

所以咋整,难道要先得到它的镜像二叉树吗?

那这样不是还要去递归?也太麻烦了吧!

其实不然,我们其实直接把前序遍历的代码拿过来,改变一下入栈的顺序即可。

本来前序遍历是先入栈右孩子,再入栈左孩子;我们改成先入栈左孩子,再入栈右孩子。

这样遍历下来,得到的顺序就是镜像二叉树的前序遍历!

然后将遍历的结果倒置即可!

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
if(root==null)return res;
//借助栈进行遍历
Stack<TreeNode> s = new Stack<>();
s.push(root);
while(!s.isEmpty()){
TreeNode t = s.pop();
res.add(t.val);
if(t.left!=null){
s.push(t.left);
}
if(t.right!=null){
s.push(t.right);
}
}
Collections.reverse(res);
return res;
}

结果如下:

其实还有一种方法:就是还是借助栈,不过额外还需要两个指针,一个之前当前栈顶元素,另一个指向前一个遍历的元素。

总体思想就是:先入栈根节点,进入循环:如果当前结点左右子节点为空或上一个访问的结点为当前结点的子节点时,当前结点出栈。否则就将右孩子和左孩子入栈!

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
if(root==null)return res;
//借助栈和curr指针进行遍历
Stack<TreeNode> s = new Stack<>();
s.push(root);
TreeNode curr,pre=null;
while(!s.isEmpty()){
curr = s.peek();
//如果当前结点左右子节点为空或上一个访问的结点为当前结点的子节点时,当前结点出栈
if((curr.left==null && curr.right==null) ||
(pre!=null && (pre==curr.left || pre==curr.right))){
res.add(curr.val);
pre = curr;
s.pop();
}else{
//先将右结点压栈
if(curr.right!=null)s.push(curr.right);
//再将左结点入栈
if(curr.left!=null)s.push(curr.left);
}
}
return res;
}

结果如下:

中序遍历

中序遍历:顺序是 左节点-》根节点-》右节点

即:[8,4,9,2,5,1,6,3,7]

如果前面后序遍历的第二种方法都彻底明白的话,中序遍历肯定分分钟就能想出来。

借助栈和一个curr指针即可。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
//通过栈和一个curr指针实现
Stack<TreeNode> s = new Stack<>();
TreeNode curr = root;
while(curr!=null || !s.isEmpty()){
if(curr!=null){
s.push(curr);
curr = curr.left;
}else{
/**
TreeNode t = s.pop();
res.add(t.val);
curr = t.right;
**/
//借助curr指针来节省内存
curr = s.pop();
res.add(curr.val);
curr = curr.right;
}
}
return res;
}

结果如下:

OK,这些思想很重要!