[LeetCode] 145. Binary Tree Postorder Traversal - 문제풀이

Description

주어진 이진 트리를 후위순회(postorder)하며 결과를 반환하는문제입니다.

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

Example 1:

Input: root = [1,null,2,3]
Output: [3,2,1]

Example 2:

Input: root = []
Output: []

Example 3:

Input: root = [1]
Output: [1]

Constraints:

• The number of the nodes in the tree is in the range [0, 100].
• 100 <= Node.val <= 100

Follow up:

Recursive solution is trivial, could you do it iteratively?

Solution 1. 재귀호출(Recursion)

public List<Integer> postorderTraversal(TreeNode root) {
    // 1. Recursion
    List<Integer> list = new ArrayList<Integer>();
    postorderTraversal(root,list);
    return list;

}
private void postorderTraversal(TreeNode node,List<Integer> list) {
    if(node == null){return;}
    postorderTraversal(node.left,list);
    postorderTraversal(node.right,list);
    list.add(node.val);
}

재귀호출을 통해 left > right > root순으로 반복 호출하며 기록해 나갑니다.

Solution 2. 반복(Iteration)

public List<Integer> postorderTraversal2(TreeNode root) {
    // 2. Iteration
    List<Integer> list = new ArrayList<Integer>();
    if(root==null){return list;}
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);
    while(!stack.isEmpty()) {
        TreeNode curr = stack.pop();
        list.add(0,curr.val);
        if(curr.left!=null) stack.push(curr.left);
        if(curr.right!=null) stack.push(curr.right);
    }
    return list;

}

Stack과 반복문을 이용한 방법입니다. left > right > root 방향의 반대로 읽을 수 있도록 root > right > left순으로 기록하되 리스트에 쓸 때 하나씩 shift되며 역순으로 데이터를 넣어줍니다.

Reference

Loading Question... - LeetCode