非递归遍历二叉树Java实现

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了非递归遍历二叉树Java实现，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2894字，纯文字阅读大概需要5分钟。

内容图文

2018-10-03 20:16:53

非递归遍历二叉树是使用堆栈来进行保存，个人推荐使用双while结构，完全按照遍历顺序来进行堆栈的操作，当然在前序和后序的遍历过程中还有其他的压栈流程。

一、Binary Tree Preorder Traversal

问题描述：

问题求解：

先序遍历就是在第一次访问到节点的时候将其值进行打印，然后递归打印其左子树，最后递归打印其右子树。

解法一、双while

    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        while (!stack.isEmpty() || root != null) {
            while (root != null) {
                res.add(root.val);
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            root = root.right;
        }
        return res;
    }

解法二、

可以使用一个栈来模拟这种操作：

首先将root压栈；

每次从堆栈中弹出栈顶元素，表示当前访问的元素，对其进行打印；

依次判断其右子树，左子树是否非空，并进行压栈操作，至于为什么先压栈右子树，因为先压栈的后弹出，左子树需要先访问，因此后压栈；

重复直到栈为空。

/**
 * 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) {
        if (root == null) return new ArrayList<>();
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode cur = stack.pop();
            res.add(cur.val);
            if (cur.right != null) stack.push(cur.right);
            if (cur.left != null) stack.push(cur.left);
        }
        return res;
    }
}

 

二、Binary Tree Inorder Traversal

问题描述：

问题求解：

双while大法。

    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        while (!stack.isEmpty() || root != null) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            res.add(root.val);
            root = root.right;
        }
        return res;
    }

 

三、Binary Tree Postorder Traversal

问题描述：

问题求解：

后序遍历的非递归版本是最有技巧性的，难度相对高一点，但其实是可以转换成前序遍历的。

后序遍历的顺序是左右中，因此只需要按中右左遍历，再reverse一下即可。

解法一、双while大法

/**
 * 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<>();
        Stack<TreeNode> stack = new Stack<>();
        while (!stack.isEmpty() || root != null) {
            while (root != null) {
                res.add(0, root.val);
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            root = root.right;
        }
        return res;
    }
}

解法二、

    public List<Integer> postorderTraversal(TreeNode root) {
        if (root == null) return new ArrayList<>();
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        stack.add(root);
        while (!stack.isEmpty()) {
            TreeNode cur = stack.pop();
            res.add(0, cur.val);
            if (cur.left != null) stack.add(cur.left);
            if (cur.right != null) stack.add(cur.right);
        }
        return res;
    }

 

内容总结

以上是互联网集市为您收集整理的非递归遍历二叉树Java实现全部内容，希望文章能够帮你解决非递归遍历二叉树Java实现所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---