二叉树遍历详解（包含非递归实现）
文章目录
二叉树遍历详解（包含非递归实现）一、基本遍历规则二、前序遍历实现三、后序遍历实现四、中序遍历
一、基本遍历规则
给出一个二叉树如下图所示。
前序遍历首先访问根节点，然后遍历左子树，最后右子树，即中 左 右。前序遍历结果为：F B A D C E G I H
中序遍历首先遍历左子树，然后访问根节点，最后右子树，即左 中 右。中序遍历结果为：A B C D E F G H I
后序遍历首先遍历左子树，然后遍历右子树，最后根节点，即左 右 中。后序遍历结果为：A C E D B H I G F
定义树的数据结构如下
public class TreeNode {
int val
;
TreeNode left
;
TreeNode right
;
TreeNode(int x
) { val
= x
; }
}
二、前序遍历实现
递归实现 递归思路很简单，按前序遍历的规则即可，先访问根节点，然后递归访问左子树，最后递归访问右子树，递归返回条件为当前节点为空。
List
<Integer> res
= new ArrayList<>();
public void preorderTraversal(TreeNode root
){
if(node
== null
) return;
res
.add(node
.val
);
preorderTraversal(node
.left
);
preorderTraversal(node
.right
);
}
非递归实现 非递归实现较递归略复杂，主要思路是借助栈来记录运行过程中的节点。在迭代时首先访问根节点，由于栈具有先进后出的特点，故先将右孩子入栈，最后将左孩子入栈，这样在下次迭代时，左孩子首先被弹出，其次是右孩子，满足前序遍历的规律。
public List
<Integer> preorderTraversal(TreeNode root
) {
List
<Integer> list
= new ArrayList<Integer>();
LinkedList
<TreeNode> stack
= new LinkedList<>();
if(root
== null
) return list
;
stack
.add(root
);
while(!stack
.isEmpty()){
TreeNode temp
= stack
.pollLast();
list
.add(temp
.val
);
if(temp
.right
!= null
){
stack
.add(temp
.right
);
}
if(temp
.left
!= null
){
stack
.add(temp
.left
);
}
}
return list
;
}
三、后序遍历实现
递归实现 递归思路同上，不在累述。
List
<Integer> res
= new ArrayList<>();
public void preorderTraversal(TreeNode root
){
if(node
== null
) return;
preorderTraversal(node
.left
);
preorderTraversal(node
.right
);
res
.add(node
.val
);
}
非递归实现 后序遍历的迭代方法实现可以类比前序遍历。首先我们知道前序遍历的遍历顺序为中 左 右，而后序遍历的顺序为左 右 中，中 左 右到左 右 中的可以由下图变换获取：
所以只需在前序遍历的代码上略做改动即可
public List
<Integer> postorderTraversal(TreeNode root
) {
LinkedList
<Integer> list
= new LinkedList<>();
Stack
<TreeNode> stack
= new Stack<>();
if(root
== null
)return list
;
stack
.push(root
);
while(!stack
.isEmpty()){
TreeNode node
= stack
.pop();
list
.addFirst(node
.val
);
if(node
.left
!= null
)stack
.push(node
.left
);
if(node
.right
!= null
) stack
.push(node
.right
);
}
return list
;
}
四、中序遍历
递归实现 思路同上。
List
<Integer> res
= new ArrayList<>();
public void preorderTraversal(TreeNode root
){
if(node
== null
) return;
preorderTraversal(node
.left
);
res
.add(node
.val
);
preorderTraversal(node
.right
);
}
非递归实现 按中序遍历顺序，每到一个节点A,因为根的访问在中间，所以先将A入栈。然后遍历左子树，接着访问 A,最后遍历右子树。在访问完A后，A就可以出栈了。
public List
< Integer
> inorderTraversal(TreeNode root
) {
List
< Integer
> res
= new ArrayList < > ();
Stack
< TreeNode
> stack
= new Stack < > ();
TreeNode curr
= root
;
while (curr
!= null
|| !stack
.isEmpty()) {
while (curr
!= null
) {
stack
.push(curr
);
curr
= curr
.left
;
}
curr
= stack
.pop();
res
.add(curr
.val
);
curr
= curr
.right
;
}
return res
;
}
