首页 > 代码库 > [leetcode] Binary Tree Postorder Traversal

[leetcode] Binary Tree Postorder Traversal

题目:(Tree ,Stack)

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].

题解:


binary tree 三部曲里面最难的一个。多看看。

/** * Definition for binary tree * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode(int x) { val = x; } * } */public class Solution {    public ArrayList<Integer> postorderTraversal(TreeNode root) {       ArrayList<Integer> result = new ArrayList<Integer>();       if(root==null)            return result;              Stack<TreeNode> stack=new Stack<TreeNode>();       stack.push(root);       TreeNode prev=null;              while(!stack.isEmpty()){           TreeNode current=stack.peek();           if(prev==null||prev.left==current||prev.right==current)           {               if(current.left!=null)                   stack.push(current.left);               else if(current.right!=null)                   stack.push(current.right);               else               {                   stack.pop();                   result.add(current.val);               }           }else if(prev==current.left)           {               if(current.right!=null)                   stack.push(current.right);                else               {                   stack.pop();                   result.add(current.val);               }           }else           {               stack.pop();               result.add(current.val);           }           prev=current;       }       return result;    }}

 

[leetcode] Binary Tree Postorder Traversal