897.递增顺序查找树

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

一、题目描述

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

示例 ：

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 范围内的唯一整数值。

二、题解

1.递归

1.1 思路

参考了rebellious_robot的题解

  1. 声明一个父节点指针，协助递归过程
  2. 向左递归访问，如果孩子节点为空，则返回父节点
  3. 令孩子节点的左孩子为空
  4. 孩子节点的右孩子则为：递归访问父节点的右孩子

父节点的作用是为了递归遍历右子树的，如果没有这个父节点，那么在递归函数的一次完整的执行过程中，无法访问递归右子树。

1.2 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
struct TreeNode *help(struct TreeNode *child, struct TreeNode *father)
{
    if (child == NULL)
        return father;
    struct TreeNode *cur = help(child->left, child);
    child->left = NULL;
    child->right = help(child->right, father);
    return cur;
}
struct TreeNode *increasingBST(struct TreeNode *root)
{
    return help(root, NULL);
}

2.迭代+构建新树

2.1 思路

  1. 中序遍历，遍历结果存储在数组中
  2. 借助数组，创建一颗新树

2.2 代码

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
30
31
32
33
34
35
36
37
38
struct TreeNode *increasingBST(struct TreeNode *root)
{
    if (root == NULL)
        return NULL;
    struct TreeNode *stack[100], *p = root;
    int stackTop = -1;
    int arr[100];
    int arrTop = -1;

    while (stackTop != -1 || p != NULL)
    {
        while (p != NULL)
        {
            stack[++stackTop] = p;
            p = p->left;
        }
        p = stack[stackTop--];
        arr[++arrTop] = p->val;
        p = p->right;
    }

    struct TreeNode *res = (struct TreeNode *)malloc(1 * sizeof(struct TreeNode));
    res->left = NULL;
    res->right = NULL;
    res->val = arr[0];
    p = res;
    for (int i = 1; i <= arrTop; i++)
    {
        p->left = NULL;
        struct TreeNode *cur = (struct TreeNode *)malloc(1 * sizeof(struct TreeNode));
        cur->left = NULL;
        cur->right = NULL;
        cur->val = arr[i];
        p->right = cur;
        p = p->right;
    }
    return res;
}