Press "Enter" to skip to content

Posts tagged as “modify”

花花酱 LeetCode 897. Increasing Order Search Tree

Problem

Given a tree, rearrange the tree in in-order so that the leftmost node in the tree is now the root of the tree, and every node has no left child and only 1 right child.

Example 1:
Input: [5,3,6,2,4,null,8,1,null,null,null,7,9]

       5
      / \
    3    6
   / \    \
  2   4    8
 /        / \ 
1        7   9

Output: [1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9]

 1
  \
   2
    \
     3
      \
       4
        \
         5
          \
           6
            \
             7
              \
               8
                \
                 9

Note:

  1. The number of nodes in the given tree will be between 1 and 100.
  2. Each node will have a unique integer value from 0 to 1000.

Solution: In-order traversal

root = 5
inorder(root.left) 之后
self.prev = 4
(1-4)已经处理完了,这时候的树是很奇怪的一个形状,3即是2的右子树,又是5的左子树。
   1
    \
     2    5
      \  /  \ 
       3     6
        \     \
 prev -> 4     8
             /  \
            7    9
—————————
5.left = None # 把5->3的链接断开
5
 \
  6
   \
    8
   /  \
  7    9
—————————–
self.prev.right = root  <=> 4.right = 5
把5接到4的右子树
1
 \
  2
   \
    3
     \
      4
       \
        5 <– prev
         \
          6
           \
            8
          /   \
         7     9
self.prev = root <=> prev = 5
inorder(5.right) <=> inorder(6) 然后再去递归处理6(及其子树)即可。

Time complexity: O(n)

Space complexity: O(n)

C++

Java

Python3