美文网首页
二叉树后序非递归遍历

二叉树后序非递归遍历

作者: I讨厌鬼I | 来源:发表于2019-06-28 16:42 被阅读0次

    题目描述

    Given a binary tree, return the postorder traversal of its nodes' values.

    input:

    Given binary tree{1,$,2,3},
       1
        \
         2
        /
       3
    

    output:

    [3,2,1]
    

    Note:

    Recursive solution is trivial, could you do it iteratively?

    思路:

    使用栈存储节点,如果有左子树,就继续往左边走,如果没有左子树,则看看栈顶节点的右子树,如果右子树不为空且没有遍历过则往右子树走,如果为空或者右子树已经被遍历过,就弹出堆栈,且把last设为该节点表明该节点是上一次被遍历过的节点。

    代码:

    /**
     * Definition for binary tree
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    import java.util.*;
    
    public class Solution {
        public ArrayList<Integer> postorderTraversal(TreeNode root) {
            ArrayList<Integer> res = new ArrayList();
            Stack<TreeNode> s = new Stack();
            TreeNode last = null;
            TreeNode cur = root;
            if (root == null){
                return res;
            }
            while(cur != null || !s.empty()){
                while(cur != null){
                    s.push(cur);
                    cur = cur.left;
                }
                cur = s.peek();
                if(cur.right != null && last != cur.right){
                    cur = cur.right;
                }else{
                    cur = s.pop();
                    res.add(cur.val);
                    last = cur;
                    cur = null;
                }
            }
            return res;
        }
    }
    

    相关文章

      网友评论

          本文标题:二叉树后序非递归遍历

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