Java二叉树前中后序的非递归实现

古城微笑少年丶 2024-04-28 07:37 18阅读 0赞

#### Java二叉树前中后序的非递归实现 ####

*  ♈️1.二叉树前序非递归遍历实现♈️
 *  ♉️2.二叉树中序非递归遍历实现♉️
 *  ♋️3.二叉树后序非递归遍历实现♋️

**大家好，我是晓星航。今天为大家带来的是 Java二叉树前中后序的非递归实现 的讲解！?**

## ♈️1.二叉树前序非递归遍历实现♈️ ##

二叉树前序非递归遍历实现 [OJ链接][OJ]

![202303311035794.png][] ![202303311035467.png][] ![202303311035026.png][]

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode() {}
     *     TreeNode(int val) { this.val = val; }
     *     TreeNode(int val, TreeNode left, TreeNode right) {
     *         this.val = val;
     *         this.left = left;
     *         this.right = right;
     *     }
     * }
     */
    /* class Solution {
        public List<Integer> preorderTraversal(TreeNode root) {
            List<Integer> list = new ArrayList<>();
            if (root == null) {
                return list;
            }
            list.add(root.val);
            List<Integer> leftTree = preorderTraversal(root.left);
            list.addAll(leftTree);
            List<Integer> rightTree = preorderTraversal(root.right);
            list.addAll(rightTree);
            return list;
        }
    }*/
    class Solution {
        
        public List<Integer> preorderTraversal(TreeNode root) {
        
    
            List<Integer> ret = new ArrayList<>();
    
            Stack<TreeNode> stack = new Stack<>();
            TreeNode cur = root;
    
            while (cur != null || !stack.isEmpty()) {
        
                while (cur != null) {
        
                    stack.push(cur);
    //              System.out.print(cur.val + " ");
                    ret.add((int) cur.val);
                    cur = cur.left;
                }
                
                TreeNode top = stack.pop();
                cur = top.right;
            }
            return ret;
        }
    }

思路：创建一个树的结点cur来遍历我们的二叉树，并在cur每遍历一个元素，我们的ret链表就添加一个cur遍历的元素的值并将该元素加入我们的栈中，然后在二叉树左边遍历完毕后我们开始弹出左边的元素并开始遍历右边的元素，在cur(遍历元素)和栈中元素不为空时一直循环即可。(根左右)

![202303311036116.png][] ![202304011857042.png][]

## ♉️2.二叉树中序非递归遍历实现♉️ ##

二叉树中序非递归遍历实现[OJ链接][OJ 1]

![202303311036524.png][] ![202303311036662.png][]

思路：创建一个树的结点cur来遍历我们的二叉树，并用cur遍历每一个元素，在二叉树左边遍历完毕后，我们的ret链表就添加一个cur遍历的元素的值并将该元素加入我们的栈中，然后我们开始弹出左边的元素并开始遍历右边的元素，在cur(遍历元素)和栈中元素不为空时一直循环即可。(左根右)

![202303311037769.png][] ![202304011858499.png][]

## ♋️3.二叉树后序非递归遍历实现♋️ ##

二叉树后序非递归遍历实现[OJ链接][OJ 2]

![202303311037389.png][] ![202303311037511.png][]

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode() {}
     *     TreeNode(int val) { this.val = val; }
     *     TreeNode(int val, TreeNode left, TreeNode right) {
     *         this.val = val;
     *         this.left = left;
     *         this.right = right;
     *     }
     * }
     */
    class Solution {
        
        public List<Integer> postorderTraversal(TreeNode root) {
        
            List<Integer> ret = new ArrayList<>();
            Stack<TreeNode> stack = new Stack<>();
            TreeNode cur = root;
            TreeNode prev = null;
            while (cur != null || !stack.isEmpty()) {
        
                while (cur != null) {
        
                    stack.push(cur);
                    cur = cur.left;
                }
                TreeNode top = stack.peek();
                if (top.right == null || top.right == prev) {
        
                    stack.pop();
                    ret.add(top.val);
                    prev = top;
                } else {
        
                    cur = top.right;
                }
            }
            return ret;
        }
    }

思路：创建一个树的结点cur来遍历我们的二叉树，并用cur遍历每一个元素，在二叉树左边遍历完毕后，我们开始弹出左边的元素并开始遍历右边的元素，在左右元素都遍历完后我们的ret链表就添加一个cur遍历的元素的值并将该元素加入我们的栈中，在cur(遍历元素)和栈中元素不为空时一直循环即可。(左右根)

![202303311037438.png][] ![202304011859474.png][]

*感谢各位读者的阅读，本文章有任何错误都可以在评论区发表你们的意见，我会对文章进行改正的。如果本文章对你有帮助请动一动你们敏捷的小手点一点赞，你的每一次鼓励都是作者创作的动力哦！?*

[OJ]: https://leetcode.cn/problems/binary-tree-preorder-traversal/
[202303311035794.png]: https://7078909xxh.oss-cn-shanghai.aliyuncs.com/csdn图床专用区/202303311035794.png
[202303311035467.png]: https://7078909xxh.oss-cn-shanghai.aliyuncs.com/csdn图床专用区/202303311035467.png
[202303311035026.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/28/9bc1923913424fd6954b539b353cf672.png
[202303311036116.png]: https://7078909xxh.oss-cn-shanghai.aliyuncs.com/csdn图床专用区/202303311036116.png
[202304011857042.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/28/19044e9477a44cf983e9076bf8d3037d.png
[OJ 1]: https://leetcode.cn/problems/binary-tree-inorder-traversal/
[202303311036524.png]: https://7078909xxh.oss-cn-shanghai.aliyuncs.com/csdn图床专用区/202303311036524.png
[202303311036662.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/28/2d7a7416bb7e4ee6984213d347a2dedc.png
[202303311037769.png]: https://7078909xxh.oss-cn-shanghai.aliyuncs.com/csdn图床专用区/202303311037769.png
[202304011858499.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/28/6f4330434f2b4709b7d95fbd0763949a.png
[OJ 2]: https://leetcode.cn/problems/binary-tree-postorder-traversal/
[202303311037389.png]: https://7078909xxh.oss-cn-shanghai.aliyuncs.com/csdn图床专用区/202303311037389.png
[202303311037511.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/28/3b3fe46625894897a1e2e0b2fde70f90.png
[202303311037438.png]: https://7078909xxh.oss-cn-shanghai.aliyuncs.com/csdn图床专用区/202303311037438.png
[202304011859474.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/28/36a46d55bb5b4beab4e56a92dcd650ef.png