题解 | #二叉树的后序遍历#

二叉树的后序遍历

http://www.nowcoder.com/practice/32af374b322342b68460e6fd2641dd1b

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @return int整型ArrayList
     */
    public ArrayList<Integer> postorderTraversal(TreeNode root) {
        ArrayList<Integer> list = new ArrayList<>();
        //迭代法 ,先实现根 右 左 再reverse
        //递归的本质就是栈
        if (root == null) return list;
        Stack<TreeNode> stk = new Stack<>();
        stk.push(root);
        while (!stk.isEmpty()) {
            //栈顶出来
            TreeNode top = stk.pop();
            list.add(top.val);
            //压入左再压入右--->我们访问的顺序就是根 右 左
            if (top.left != null) stk.push(top.left);
            if (top.right != null) stk.push(top.right);
        }
        Collections.reverse(list);
        return list;

    }
}
全部评论

相关推荐

07-08 13:48
门头沟学院 C++
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-04 14:23
steelhead:你回的有问题,让人感觉你就是来学习的
点赞 评论 收藏
分享
06-07 17:17
嘉兴学院 教师
心爱的idea:你孩
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务