LeetCode: Binary Tree Postorder Traversal 解题报告

Binary Tree Postorder Traversal

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

For example:
Given binary tree {1,#,2,3},
   1
    \
     2
    /
   3
return [3,2,1].

Note: Recursive solution is trivial, could you do it iteratively?

Show Tags
Have you met this question in a real interview? Yes No
Discuss

SOLUTION 1:

递归解法

 public List<Integer> postorderTraversal1(TreeNode root) {

         List<Integer> ret = new ArrayList<Integer>();

         dfs(root, ret);

         return ret;

     }

     // Solution 1: rec

     public void dfs(TreeNode root, List<Integer> ret) {

         if (root == null) {

             return;

         }

         dfs(root.left, ret);

         dfs(root.right, ret);

         ret.add(root.val);

     }

SOLUTION 2:

/**
     * 后序遍历迭代解法
     * http://www.youtube.com/watch?v=hv-mJUs5mvU
     * http://blog.csdn.net/tang_jin2015/article/details/8545457
     * 从左到右的后序与从右到左的前序的逆序是一样的，所以就简单喽！哈哈
     * 用另外一个栈进行翻转即可喽
     */

 // Solution 2: iterator

     public List<Integer> postorderTraversal(TreeNode root) {

         List<Integer> ret = new ArrayList<Integer>();

         if (root == null) {

             return ret;

         }

         Stack<TreeNode> s = new Stack<TreeNode>();

         Stack<Integer> out = new Stack<Integer>();

         s.push(root);

         while (!s.isEmpty()) {

             TreeNode cur = s.pop();

             out.push(cur.val);

             if (cur.left != null) {

                 s.push(cur.left);

             }

             if (cur.right != null) {

                 s.push(cur.right);

             }

         }

         while (!out.isEmpty()) {

             ret.add(out.pop());

         }

         return ret;

     }

GITHUB:

https://github.com/yuzhangcmu/LeetCode_algorithm/blob/master/tree/PostorderTraversal.java

巴特西

LeetCode: Binary Tree Postorder Traversal 解题报告

最新文章

热门文章