欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

二叉树的前序遍历、中序遍历和后序遍历(迭代解法)

程序员文章站 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. 访问根节点
  2. 访问左子树
  3. 访问右子树

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. 二叉树的中序遍历

二叉树的中序遍历过程:

  1. 遍历左子树
  2. 访问根节点
  3. 遍历右子树

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 优秀题解

二叉树后序遍历步骤:

  1. 遍历左子树
  2. 遍历右子树
  3. 访问根节点

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 迭代解法

算法思想:

  1. 前序遍历的过程 是 中左右
  2. 将其转化成 中右左。也就是压栈的过程中优先压入左子树,在压入右子树。
  3. 然后将这个结果返回来,这里是利用栈先进后出倒序打印,则为左右中
/**
 * 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;
    }
}