LeetCode897-递增顺序查找树

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/increasing-order-search-tree/

中文链接：https://leetcode-cn.com/problems/increasing-order-search-tree/

题目详述

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

示例 ：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
输入：[5,3,6,2,4,null,8,1,null,null,null,7,9]

       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

提示：

  1. 给定树中的结点数介于 1 和 100 之间。
  2. 每个结点都有一个从 0 到 1000 范围内的唯一整数值。

题目详解

  • 进行中序遍历把结点按照要求重新连起来即可。
  • 关键在于记录当前结点的前一个结点。
  • 注意操作完成后设置当前结点的 left = null。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class LeetCode_00897 {

    public TreeNode increasingBST(TreeNode root) {
        TreeNode dummy = new TreeNode(0);
        inOrder(root, new TreeNode[]{dummy});
        return dummy.right;
    }

    private void inOrder(TreeNode root, TreeNode[] pre) {
        if (root == null) {
            return;
        }
        inOrder(root.left, pre);
        root.left = null;
        pre[0].right = root;
        pre[0] = pre[0].right;
        inOrder(root.right, pre);
    }
}

可以把上面的递归形式改成非递归形式。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class LeetCode_00897 {

    public TreeNode increasingBST(TreeNode root) {
        TreeNode dummy = new TreeNode(0);
        TreeNode pre = dummy;
        Stack<TreeNode> stack = new Stack<>();
        while (!stack.isEmpty() || root != null) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            root.left = null;
            pre.right = root;
            pre = root;
            root = root.right;
        }
        return dummy.right;
    }
}
  • 可以换一种思路，在递归的过程中传递一个尾节点。
  • 进行中序遍历，按照要求改变指针指向。
  • 往左子树递归调用传入的是当前结点，表示左子树链上当前结点。
  • 往右子树递归调用传入尾节点，表示右子树脸上尾结点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class LeetCode_00897 {

    public TreeNode increasingBST(TreeNode root) {
        return inOrder(root, null);
    }

    private TreeNode inOrder(TreeNode root, TreeNode tail) {
        if (root == null) {
            return tail;
        }
        TreeNode head = inOrder(root.left, root);
        root.left = null;
        root.right = inOrder(root.right, tail);
        return head;
    }
}