.leetcode(114. Flatten Binary Tree to Linked List)

https://leetcode.com/problems/flatten-binary-tree-to-linked-list/

 

2. 2022.03.03 시도 

소요시간: 8분(3분 구상, 5분 코딩, recursion), 10분(iterative)

// recursion
class Solution {
    public void flatten(TreeNode root) {
        if (root == null) {
            return;
        }
        
        if (root.left == null) {
            flatten(root.right);
            return;
        }
        
        TreeNode leftRightMost = root.left;
        while(leftRightMost.right != null) {
            leftRightMost = leftRightMost.right;
        }
        
        TreeNode right = root.right;
        root.right = root.left;
        root.left = null;
        leftRightMost.right = right;
        
        flatten(root.right);
    }
}

// iteration
class Solution {
    public void flatten(TreeNode root) {
        if (root == null) {
            return;
        }
        
        while(root != null) {
            if (root.left != null) {
                TreeNode leftRightMost = root.left;
                while(leftRightMost.right != null) {
                    leftRightMost = leftRightMost.right;
                }
                
                TreeNode right = root.right;
                root.right = root.left;
                root.left = null;
                leftRightMost.right = right;
            }
            
            root = root.right;
        }
    }
}

풀이 접근 과정

1, 왼쪽이 있으면 그것의 가장 오른쪽을 찾고
2, 왼쪽을 루트의 오른쪽으로 가져온다.
3, 1번에다가 루트의 오른쪽 부분을 붙여준다.
4, 그 다음 오른쪽으로 전진하고 반복한다.

 

느낀점

• Morris Traversal 라는 이름이 기억이 안났다. 이건 기억해놓자.
• 이전에 풀었던 문제이기도 하다.

---

 

1. 2022.01.27 시도

소요시간: 11분

#iterative
class Solution {
    public void flatten(TreeNode root) {
        if (root == null) {
            return;
        }

        LinkedList<TreeNode> stack = new LinkedList<>();
        stack.push(root);

        while(!stack.isEmpty()) {
            TreeNode cur = stack.pop(); 
            if (cur.left != null) {
                TreeNode temp = cur.right;
                cur.right = cur.left;
                cur.left = null;
                stack.push(cur.right);
                while(cur.right != null) {
                    cur = cur.right;
                }
                cur.right = temp;
            } else if (cur.right != null) {
                stack.push(cur.right);   
            }
        }
    }
}

 

풀이 접근 과정

Morris Traversal이라고 해서 "94. Binary Tree Inorder Traversal"에서 분명히 이용해서 풀었다.

 

느낀점

• 사실 Morris라는 이름은 기억이 안났지만 오려서 붙여넣기 했던 기억은 있어서 그대로 코드를 짤 수 있었다.
• recursion으로 푸는건 조금 색다르다. return에서 rightmost를 결정하면서 내려주기 때문에 따로 whil을 안해도 된다. if문만 조심해서 설정해두면 깔끔하게 코드를 짤 수 있다.

class Solution {
    public void flatten(TreeNode root) {
        doFlatten(root);
    }

    public TreeNode doFlatten(TreeNode root) {
        if (root == null) {
            return null;
        }
        if (root.left == null && root.right == null) {
            return root;
        }


        TreeNode left = doFlatten(root.left);
        TreeNode right = doFlatten(root.right);

        if (left != null) {
            left.right = root.right;
            root.right = root.left;
            root.left = null;
        }

        return right == null ? left : right;
    }
}

 

---

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

반응형