LeetCode——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?
두 갈래 나무의 후속 역행 (왼쪽-오른쪽-뿌리).비귀속을 사용할 수 있습니까?
귀속:
public class BinaryTreePostorderTraversal {
    public List<Integer> postorderTraversal(TreeNode root) {
    	List<Integer> list = new ArrayList<Integer>();
        if(root == null)
        	return list;
        list.addAll(postorderTraversal(root.left));
        list.addAll(postorderTraversal(root.right));
        list.add(root.val);
        return list;
    }
    // Definition for binary tree
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }
}

비귀속:
    public List<Integer> postorderTraversal(TreeNode root){
    	List<Integer> list = new ArrayList<Integer>();
    	if(root == null)
    		return list;
    	Stack<TreeNode> stack = new Stack<TreeNode>();
    	stack.push(root);// 
    	while(!stack.isEmpty()){
    		TreeNode current = stack.peek();
    		// 
    		if(current.left == null && current.right == null){
    			list.add(current.val);
    			stack.pop();
    		}
    		if(current.left != null){
    			stack.push(current.left);
    			current.left = null;
    			continue;
    		}
    		if(current.right != null){
    			stack.push(current.right);
    			current.right = null;
    			continue;
    		}
    	}
    	return list;
    }

좋은 웹페이지 즐겨찾기