LeetCode : Binary Tree Postorder Traversal 二叉树后序遍历递归迭代

绝地灬酷狼 2021-06-24 16:10 304阅读 0赞

**试题：**  
Given a binary tree, return the postorder traversal of its nodes’ values.

Example:

Input: \[1,null,2,3\]  
1  
  
2  
/  
3

Output: \[3,2,1\]  
Follow up: Recursive solution is trivial, could you do it iteratively?  
**代码：**  
递归

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        List<Integer> out = new ArrayList<>();
        public List<Integer> postorderTraversal(TreeNode root) {
            if(root==null) return out;
            postorderTraversal(root.left);
            postorderTraversal(root.right);
            out.add(root.val);
            return out;
        }
    }

迭代：使用root-right-left，再反转形式

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        public List<Integer> postorderTraversal(TreeNode root) {
            List<Integer> out = new ArrayList<>();
            Stack<TreeNode> stack = new Stack<>();
            stack.push(root);
            while(!stack.isEmpty()){
                TreeNode tmp = stack.pop();
                if(tmp==null) continue;
                out.add(tmp.val);
                stack.push(tmp.left);
                stack.push(tmp.right);
            }
            Collections.reverse(out);
            return out;
        }
    }