[Leetcode] 114. 이 진 트 리 를 링크 로 펼 칩 니 다.

제목.
이 진 트 리 를 지정 하여 제자리 에서 링크 로 펼 칩 니 다.
이 진 트 리
    1
   / \
  2   5
 / \   \
3   4   6

다음으로 펼 치기:
1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6

해제
이것 은 비교적 전형 적 인 문제 라 고 할 수 있다. 블 로 거들 이 면접 을 빨리 볼 때 원래 의 문제 이다.처음에 생각해 보 니 재 귀적 인 구 해 가 좋 지 않 을 까 생각 했 지만 재 귀적 할 때 주의해 야 할 점 은 오른쪽 나무 로 먼저 돌아 간 다음 에 오른쪽 나무 가 펼 쳐 진 후의 체인 표 두 를 기록 해 야 한 다 는 것 이다.그리고 다시 돌아 와 서 왼쪽 나무의 마지막 사슬 을 오른쪽 나무의 사슬 머리 까지 풀 어 줍 니 다.이 를 바탕 으로 우 리 는 pre 포인터 로 오른쪽 나무의 머리 결 점 을 기록 합 니 다.
class Solution {
    private TreeNode prev = null;

    public void flatten(TreeNode root) {
        if (root == null)
        return;
        flatten(root.right);
        flatten(root.left);
        root.right = prev;
        root.left = null;
        prev = root;
    }
}

재 귀적 인 방식 을 교체 하 는 방식 으로 stack 으로 바 꾸 면 좋 고 오히려 이해 하 는 것 보다 낫다.
class Solution {
    public void flatten(TreeNode root) {
        if (root == null) return;
        Stack stack = new Stack();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode current = stack.pop();
            if (current.right != null) stack.push(current.right);
            if (current.left != null) stack.push(current.left);
            if (!stack.isEmpty()) current.right = stack.peek();
            current.left = null;
        }
    }
}

문제 가 있 습 니 다.

좋은 웹페이지 즐겨찾기