二叉树的前序遍历、中序遍历和后序遍历(迭代解法)
程序员文章站
2022-06-17 19:53:48
...
前言
二叉树的非递归算法需要借助栈来完成。
Java中栈的实现类为Stack
.
方法有:
序号 | 方法描述 |
---|---|
boolean empty() | 测试堆栈是否为空。 |
Object pop( ) | 出栈,移除堆栈顶部的对象,并作为此函数的值返回该对象。 |
Object push(Object element) | 入栈,把项压入堆栈顶部。 |
Object peek( ) | 查看堆栈顶部的对象,但不从堆栈中移除它。 |
int search(Object element) | 返回对象在堆栈中的位置,以 1 为基数。 |
1、前序遍历
leetcode 144. 二叉树的前序遍历
二叉树的前序遍历的遍历过程为:
- 访问根节点
- 访问左子树
- 访问右子树
1.1 递归解法
递归算法如下:
public static void preOrderRecur(TreeNode head) {
if (head == null) {
return;
}
System.out.print(head.value + " ");
preOrderRecur(head.left);
preOrderRecur(head.right);
}
1.2 迭代解法
本质上是在模拟递归,因为在递归的过程中使用了系统栈,所以在迭代的解法中常用Stack来模拟系统栈。
算法思想:
-
首先我们应该创建一个Stack用来存放节点,首先我们想要打印根节点的数据,此时Stack里面的内容为空,所以我们优先将头结点加入Stack,然后打印。
-
之后我们应该先打印左子树,然后右子树。所以先加入Stack的就是右子树,然后左子树。
此时你能得到的流程如下:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
if(root == null){
return result;
}
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while(!stack.empty()){
TreeNode temp = stack.pop();
result.add(temp.val);
if(temp.right != null){
stack.push(temp.right);
}
if(temp.left != null){
stack.push(temp.left);
}
}
return result;
}
}
2、中序遍历
leetcode 94. 二叉树的中序遍历
二叉树的中序遍历过程:
- 遍历左子树
- 访问根节点
- 遍历右子树
2.1递归解法
public static void preOrderRecur(TreeNode head) {
if (head == null) {
return;
}
preOrderRecur(head.left);
System.out.print(head.value + " ");
preOrderRecur(head.right);
}
2.2 迭代解法
递归的调用过程是不断往左边走,当左边走不下去了,就打印节点,并转向右边,然后右边继续这个过程。
我们在迭代实现时,就可以用栈来模拟上面的调用过程。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList();
Stack<TreeNode> stack = new Stack<>();
while(!stack.empty() || root != null){
//不断往左子树方向走,每走一次就将当前节点保存到栈中
//这是模拟递归的调用
if(root != null){
stack.push(root);
root = root.left;
//当前节点为空,说明左边走到头了,从栈中弹出节点并保存
//然后转向右边节点,继续上面整个过程
}else{
TreeNode tmp = stack.pop();
res.add(tmp.val);
root = tmp.right;
}
}
return res;
}
}
3、后序遍历
leetcode 优秀题解
二叉树后序遍历步骤:
- 遍历左子树
- 遍历右子树
- 访问根节点
3.1 递归解法
public static void postOrderRecur(TreeNode head) {
if (head == null) {
return;
}
postOrderRecur(head.left);
postOrderRecur(head.right);
System.out.print(head.value + " ");
}
3.2 迭代解法
算法思想:
- 前序遍历的过程 是 中左右。
- 将其转化成 中右左。也就是压栈的过程中优先压入左子树,在压入右子树。
- 然后将这个结果返回来,这里是利用栈的先进后出倒序打印,则为左右中。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
if(root == null){
return res;
}
Stack<TreeNode> stack = new Stack<>();
Stack<TreeNode> help = new Stack<>();
stack.push(root);
while(!stack.empty()){
TreeNode node = stack.pop();
help.push(node);
if(node.left != null){
stack.push(node.left);
}
if(node.right != null){
stack.push(node.right);
}
}
while(!help.empty()){
res.add(help.pop().val);
}
return res;
}
}
推荐阅读
-
Python实现输入二叉树的先序和中序遍历,再输出后序遍历操作示例
-
PHP实现二叉树深度优先遍历(前序、中序、后序)和广度优先遍历(层次)实例详解
-
[PHP] 算法-根据前序和中序遍历结果重建二叉树的PHP实现
-
Python实现二叉树前序、中序、后序及层次遍历示例代码
-
【算法】二叉树的前序、中序、后序、层序遍历和还原。
-
PHP基于非递归算法实现先序、中序及后序遍历二叉树操作示例
-
Python二叉树的遍历操作示例【前序遍历,中序遍历,后序遍历,层序遍历】
-
L2-006 树的遍历 (后序中序求层序)
-
已知后序遍历和中序遍历求层序遍历(树的遍历)
-
C++实现LeetCode(105.由先序和中序遍历建立二叉树)