[数据结构与算法] 【算法与数据结构】 [非递归] 二叉树的先序遍历、中序遍历、后序遍历

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 【算法与数据结构】 [非递归] 二叉树的先序遍历、中序遍历、后序遍历 -> 正文阅读

[数据结构与算法]【算法与数据结构】 [非递归] 二叉树的先序遍历、中序遍历、后序遍历

二叉树的先序遍历

public int[] preorderTraversal (TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        while (!stack.empty() || root!=null){
            while (root!=null){
                list.add(root.val);
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            root = root.right;
        }
        int[] ans = new int[list.size()];
        for(int i=0;i<ans.length;i++){
            ans[i] = list.get(i);
        }
        return ans;
    }

二叉树的中序遍历非递归

public int[] inorderTraversal (TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        while (!stack.empty() || root!=null){
            while (root!=null){

                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            list.add(root.val);
            root = root.right;
        }
        int[] ans = new int[list.size()];
        for(int i=0;i<ans.length;i++){
            ans[i] = list.get(i);
        }
        return ans; // write code here
    }

二叉树的后序遍历非递归版本
因为二叉树的先序遍历是：根左右
我们可以通过改变先序顺序得到：根右左
然后对根右左进行反向遍历就可以得到左右根

public int[] postorderTraversal (TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        while (!stack.empty() || root!=null){
            while (root!=null){
                list.add(root.val);
                stack.push(root);
                root = root.right;
            }
            root = stack.pop();
            root = root.left;
        }
        int[] ans = new int[list.size()];
        for(int i=ans.length-1;i>=0;i--){
            ans[i-ans.length+1] = list.get(i);
        }
        return ans;
    }