递增顺序查找树

发表于 | 分类于 |
字数统计: 663 字 | 阅读时长 ≈ 2 分钟

题目描述：给你一个树，请你 按中序遍历 重新排列树，使树中最左边的结点现在是树的根，并且每个结点没有左子结点，只有一个右子结点。

示例：
输入：[5,3,6,2,4,null,8,1,null,null,null,7,9]

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

输出：[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
10
11
12
13
14
15
16
17
1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6
           \
            7
             \
              8
               \
                9

提示：

  1. 给定树中的结点数介于 1 和 100 之间。
  2. 每个结点都有一个从 0 到 1000 范围内的唯一整数值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
  public TreeNode increasingBST(TreeNode root) {

  }
}

方法一：中序遍历 + 构造新的树

我们在树上进行中序遍历，就可以从小到大得到树上的节点。我们把这些节点的对应的值存放在数组中，它们已经有序。接着我们直接根据数组构件题目要求的树即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
  public TreeNode increasingBST(TreeNode root) {
    List<Integer> vals = new ArrayList<>();
    inorder(root, vals);
    TreeNode ans = new TreeNode(0), cur = ans;
    for (int v: vals) {
      cur.right = new TreeNode(v);
      cur = cur.right;
    }
    return ans.right;
  }

  // 中序遍历
  private void inorder(TreeNode node, List<Integer> vals) {
    if(node == null) return;
    inorder(node.left, vals);
    vals.add(node.val);
    inorder(node.right, vals);
  }
}

复杂度分析：

  • 时间复杂度：O(N)，其中 N 是树上的节点个数
  • 空间复杂度：O(N)

执行结果：通过

  • 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户

  • 内存消耗：37.6 MB, 在所有 Java 提交中击败了20.32%的用户

方法二：中序遍历 + 更改树的连接方式

和方法一类似，我们在树上进行中序遍历，但会将树中的节点之间重新连接而不使用额外的空间。具体地，当我们遍历到一个节点时，把它的左孩子设为空，并将其本身作为上一个遍历到的节点的右孩子。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
  TreeNode cur;
  public TreeNode increasingBST(TreeNode root) {
    TreeNode ans = new TreeNode(0);
    cur = ans;
    inorder(root);
    return ans.right;
  }

  private void inorder(TreeNode node) {
    if(node == null) return;
    inorder(node.left);
    node.left = null;
    cur.right = node;
    cur = node;
    inorder(node.right);
  }
}

复杂度分析：

  • 时间复杂度：O(N)，其中 N 是树上的节点个数
  • 空间复杂度：O(H)，其中 H 是数的高度

执行结果：通过

  • 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户

  • 内存消耗：37.3 MB, 在所有 Java 提交中击败了63.66%的用户