LintCode - 두 갈래 트리를 체인 테이블로 분리하기(일반)

1294 단어
판권 성명: 본고는 블로거의 오리지널 문장으로 블로거의 허락 없이 전재할 수 없습니다.
난이도: 쉽다
요구 사항:
두 갈래 나무를 앞의 순서에 따라 두루 분해하여 가짜 체인 시계로 만들다.가짜 체인 시계란 두 갈래 나무의right 바늘로 체인 시계의next 바늘을 나타내는 것이다.
 
  null, 。

예제
              1
               \
     1          2
    / \          \
   2   5    =>    3
  / \   \          \
 3   4   6          4
                     \
                      5
                       \
                        6

생각:
/**
     * @param root: a TreeNode, the root of the binary tree
     * @return: nothing
     */
    public void flatten(TreeNode root) {
        if (root == null) {
            return;
        }
        
        Stack stack = new Stack<>();
        stack.push(root);
        
        while (!stack.empty()) {
            TreeNode node = stack.pop();
            if (node.right != null) {
                stack.push(node.right);
            }
            if (node.left != null) {
                stack.push(node.left);
            }
            
            // connect 
            node.left = null;
            if (stack.empty()) {
                node.right = null;
            } else {
                node.right = stack.peek();
            }
        }
    }

좋은 웹페이지 즐겨찾기