.leetcode(145. Binary Tree Postorder Traversal)

https://leetcode.com/problems/binary-tree-postorder-traversal/

 

1. 2022/05/11 시도

소요시간: 1분(recursive), 못품(iterative)

// recursive
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> ret = new ArrayList<>();
        recursive(root, ret);
        return ret;
    }
    
    private void recursive(TreeNode root, List<Integer> ret) {
        if (root == null) {
            return;
        }
        
        recursive(root.left, ret);
        recursive(root.right, ret);
        ret.add(root.val);
    }
}

풀이 접근 과정

recursive
- postorder이기때문에 left, right를 돌고 마지막에 add해주면 된다.

 

느낀점

• iterative는 감을 못 잡았다. 원본을 훼손하지 않고 가장 잘 푼 솔루션을 내 스타일로대로 풀어보았다.
• 기본은 preorder때의 풀이를 취하되, 중복으로 카운트가 안되도록 prev처리를 추가하였다.

// iterative
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> ret = new ArrayList<>();
        if (root == null) {
            return ret;
        }
     
        Stack<TreeNode> stack = new Stack<>();
        TreeNode current = root;
        TreeNode prev = null;
        while (current != null || !stack.isEmpty()) {
            while (current != null) {
                stack.push(current);
                current = current.left;
            }
            if (stack.peek().right != null && stack.peek().right != prev) {
                current = stack.peek().right;
                continue;
            }
            TreeNode node = stack.pop();
            ret.add(node.val);
            prev = node;
        }
        
        return ret;
    }
}

• Morris Traversal로도 풀이가 가능하다. 약간의 트릭이 필요하지만 아주 흥미로운 풀이다. 이건 나중에 다시 시도할 때를 위하여 남겨두겠다.

---

알고리즘 정리노트: .leetcode(알고리즘 문제풀이 접근)

반응형