美文网首页刷爆力扣
【30】二叉树的后序遍历

【30】二叉树的后序遍历

作者: 公孙剑人 | 来源:发表于2021-05-19 20:30 被阅读0次

    来源:力扣(LeetCode)
    链接:https://leetcode-cn.com/problems/binary-tree-postorder-traversal/

    题目

    给定一个二叉树,返回它的后序遍历。

    示例:

    输入: [1,null,2,3]
      1
        \
         2
        /
      3

    输出: [3,2,1]
    进阶: 递归算法很简单,你可以通过迭代算法完成吗?

    思路

    借鉴了力扣上一个很牛掰的解法:

    1. 后续遍历是左->右->中的顺序,那就可以自定向下,拿到中->右->左的值,倒叙后即是结果;
    2. 从root节点开始,如果不为空,入栈,并将val放在LinkedList的队头;
    3. 然后将root节点指向右子节点,继续第2步;
    4. 如果节点为空,则将上一个节点出栈,root指向其左子节点,继续第2步;
    5. 若root为空,且stack为空,入栈的节点已全部出栈,则该二叉树已经遍历完毕,返回result即可。

    代码

        public List<Integer> postorderTraversal(TreeNode root) {
            LinkedList<Integer> result = new LinkedList<>();
            Stack<TreeNode> stack = new Stack<>();
            while (root != null || !stack.isEmpty()) {
                if (root != null) {
                    stack.push(root);
                    result.addFirst(root.val);
                    root = root.right;
                } else {
                    root = stack.pop();
                    root = root.left;
                }
            }
            return result;
        }
    

    结果

    执行结果

    相关文章

      网友评论

        本文标题:【30】二叉树的后序遍历

        本文链接:https://www.haomeiwen.com/subject/dafjjltx.html