.leetcode(94. Binary Tree Inorder Traversal)

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

 

3. 2022/05/10 시도

소요시간: 2분(recursive), 13분(iterative)

// recursive
class Solution {
    public List<Integer> inorderTraversal(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);
        ret.add(root.val);
        recursive(root.right, ret);
    }
}

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

풀이 접근 과정

recursive
- 왼쪽을 가장 아래까지 접근한 후, 해당 노드부터 차근차근 저장한다.

iterative
- while문을 이용해서 stack에 모든 왼쪽노드를 저장하고 하나씩 pop해서 해당 노드를 저장하고 오른쪽 노드를 다시 stack에 넣는다.

 

느낀점

• 2번쨰보다 빨리 풀었지만 역시나 원본을 훼손하지 않고 풀지는 못했다.
• 오른쪽으로 이동하면서 푸는 방법을 다음에 꼭 풀어보면 좋겠다.
• Morris Traversal은 이번에도 생각하지 못했다. 아래에 풀이가 있으므로 풀이는 추가로 적지 않았다. 훼손없이 풀는 방법과 모리스 트래블로 푸는 방법 2가지다 기억해야겠다.

---

 

2. 2022.01.06 시도

소요시간: 3분(recursive), 30분(구상 16분, 코딩 14분, iterative)

// recursive
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> output = new ArrayList<>();
        
        
        recursive(root, output);
        
        return output;
    }
    
    private void recursive(TreeNode root, List<Integer> output) {
        if (root == null) {
            return;
        }

        recursive(root.left, output);
        output.add(root.val);
        recursive(root.right, output);
    }
}

// iterative
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        LinkedList<Integer> output = new LinkedList<>();
        if (root == null) {
            return output;
        }
        
        LinkedList<TreeNode> stack = new LinkedList<>();
        stack.push(root);
        while(!stack.isEmpty()) {
            TreeNode treeNode = stack.pop();
            if (treeNode.left != null) {
                stackLeftTree(stack, treeNode);
                continue;
            }
            output.add(treeNode.val);
            if (treeNode.right != null) {
                stack.push(treeNode.right);
            }
        }
        
        return output;
    }
    
    private void stackLeftTree(LinkedList<TreeNode> stack, TreeNode root) {
        TreeNode current = root;
        while(current != null) {
            stack.push(current);
            TreeNode temp = current.left;
            current.left = null;
            current = temp;    
        }
    }
}

풀이 접근 과정

inorder를 재귀 쓰면 정말 쉽게 풀린다 recursive메소드 만들고 돌리면 시간복잡도 O(n), 공간복잡도 O(n)으로 풀 수 있겠다 싶었다. 

이 역시 iterative로 풀 수 있겠다고 생각이 들었다. 뒤에부터 소비가 되어야하니 직감적으로 stack이 맞겠다는 생각이 들었다. 이전에 postOrder방식으로 짜두니 생각이 막혔다. left를 가운데보다 매번 먼저 넣어야하는게 잘 그려지지 않았다.

[1,2,3,4,5,6,7]이라는 treeNode를 샘플로 넣어서 inorder로 그려지는걸 보니 왼쪽을 먼저 stack에 다 넣어버리면 해결책이 나올 것이라는 생각이 들었다. 손코딩으로 계산해보니 잘 되었다.

코딩하다보니 leftNode가 있을때 left먼저 다 넣는건 어렵지 않는데 다시 순회할때보면 left를 남겨두었다가는 무한루프에 빠지겠다 싶어서 leftNode를 null로 초기화했다. 주어진 노드를 훼손하는게 마음에 걸렸지만 일단 구현이 우선이었다. null로 치환하니 순조롭게 풀렸다.

 

느낀점

• iterative에서 inorder를 풀 경우, 왼쪽 트리노드를 먼저 다 stack에 넣는다는 생각이 잘 안들었다. 이를 유념하고 있어야겠다.
• treenode를 훼손하지 않으면서도 충분히 iterative하게 풀 수도 있다. 아래와 같은 방식으로 pop을 left다음으로 해주는 것이다.

// iterative
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        LinkedList<Integer> output = new LinkedList<>();
        if (root == null) {
            return output;
        }
        
        LinkedList<TreeNode> stack = new LinkedList<>();
        TreeNode current = root;
        while(current != null || !stack.isEmpty()) {
            stackLeftTree(stack, current);
            current = stack.pop();
            output.add(current.val);
            current = current.right;
        }
        
        return output;
    }
    
    private void stackLeftTree(LinkedList<TreeNode> stack, TreeNode root) {
        TreeNode current = root;
        while(current != null) {
            stack.push(current);
            current = current.left;
        }
    }
}

• Morris Traversal은 이번에도 생각하지 못했다. 이것도 inorder일때 기억해두면 좋겠다.

// Morris Traversal
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> output = new ArrayList<>();
        
        TreeNode current = root;
        while(current != null) {
            if (current.left != null) {
                TreeNode rightestTreeNode = findRightestTreeNode(current.left);
                rightestTreeNode.right = current;
                current = current.left;
                rightestTreeNode.right.left = null;
                continue;
            }
            output.add(current.val);
            current = current.right;
        }
        
        return output;
    }
    
    private TreeNode findRightestTreeNode(TreeNode root) {
        TreeNode current = root;
        while(current.right != null) {
            current = current.right;
        }
        
        return current;
    }
}

 

---

1. 2021.01.15 시도

소요시간: 6분

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        doInorderTraversal(result, root);

        return result;
    }

    private void doInorderTraversal(List<Integer> result, TreeNode root) {
        if (root == null) {
            return;
        }

        doInorderTraversal(result, root.left);
        result.add(root.val);
        doInorderTraversal(result, root.right);
    }
}

풀이 접근 과정

왼쪽부터 읽으면 되겠다.(inorder traversal)

tree를 recursive로 읽을 때는 left,right로 분기되어 2번 호출하는데 이런 inorder로 할때는 left와 right중간에서 node를 기록하면 되겠다 싶었다.

 

느낌점

• tree를 보통 recursive하게 풀 수 있으면 stack을 써서 iterative하게도 풀 수 있으니 풀어보자.
• iteratvie하게 풀때는 inorder로 하니 반드시 왼쪽부터 먼저 push를 먼저 하도록 하는게 포인트다.
• Morris Traversal로 풀어보았다. 이 알고리즘의 핵심은 모든 Left노드를 없앤다. 따라서 지금 root에서 left가 있으면 root를 root.left로 치환하고 이전 root를 새로인 root(이전에 root.left)에게 있는 가장 오른쪽으로 옮기는게 핵심이다. 코드 구현은 아래처럼 해보면 금방 할 수 있다.

#stack을 이용해 iterative하게 풀이 
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        LinkedList<TreeNode> stack = new LinkedList<>();


        while(root != null || !stack.isEmpty()) {
            while(root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            result.add(root.val);
            root = root.right;
        }


        return result;
    }
}

# Morris Traversal
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();

        while (root != null){
            if (root.left != null) {
                TreeNode temp = root;
                root = root.left;
                TreeNode tail = root; 
                while(tail.right != null) {
                    tail = tail.right;
                }
                temp.left = null;
                tail.right = temp;
            } else {
                result.add(root.val);
                root = root.right;
            }
        }

        return result;
    }
}

---

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

 

반응형