二叉树的前中后序遍历 非递归


二叉树前序遍历

前序遍历顺序:根->左->右

    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        stack.add(root);
        while (!stack.isEmpty()) {
            TreeNode tem = stack.pop();
            if (tem != null) {
                //访问节点同时 将右,左子节点放栈顶
                res.add(tem.val);
                stack.add(tem.right);
                stack.add(tem.left);
            }
        }
        return res;
    }

二叉树中序遍历

前序遍历顺序:左->根->右

 public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode tem = root;
        while (!stack.isEmpty() || tem != null) {
            while (tem != null) {
                stack.add(tem);
                tem = tem.left;
            }
            //此时栈顶节点左子树访问完了
            TreeNode pop = stack.pop();
            if (pop != null) {
                res.add(pop.val);
                //右子树
                tem = pop.right;
            }
        }
        return res;
    }

二叉树后序遍历

前序遍历顺序:左->右->根

 public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode tem = root;
        //标识
        TreeNode last = null;
        while (!stack.isEmpty() || tem != null) {
            while (tem != null) {
                stack.add(tem);
                tem = tem.left;
            }
            last = null;
            while (!stack.isEmpty()) { //右子树返回,要循环
                TreeNode pop = stack.pop();
                if (pop.right == last) {
                    //右子树返回,访问
                    res.add(pop.val);
                    last = pop;
                } else {
                    //左子树返回,不访问
                    stack.add(pop);
                    tem = pop.right;
                    break;
                }
            }
        }
        return res;
    }
  • 作者:低调做个路人 (扫码联系作者)
  • 发表时间:2021-10-09 16:33:46
  • 版权声明:自由转载-非商用-非衍生-保持署名(创意共享3.0许可证)
  • 评论