二叉树(下)

# 二叉树（下）

# 十七、中序加后序遍历序列构造二叉树

代码随想录 (programmercarl.com) (opens new window)

106. 从中序与后序遍历序列构造二叉树 - 力扣（LeetCode） (opens new window)

105. 从前序与中序遍历序列构造二叉树 - 力扣（LeetCode） (opens new window)

# 1、题目

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
示例 1:
输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]
1
2
3
示例 2:
输入: preorder = [-1], inorder = [-1]
输出: [-1]
1
2
提示:

1 <= preorder.length <= 3000

inorder.length == preorder.length

-3000 <= preorder[i], inorder[i] <= 3000

preorder 和 inorder 均 无重复 元素

inorder 均出现在 `preorder``

``preorder` 保证为二叉树的前序遍历序列

inorder 保证为二叉树的中序遍历序列

# 2、思路

就是以后序数组的最后一个元素为切割点，先切中序数组，根据中序数组，反过来再切后序数组。一层一层切下去，每次后序数组最后一个元素就是节点元素。

106.从中序与后序遍历序列构造二叉树

说到一层一层切割，就应该想到了递归。

来看一下一共分几步：

第一步：如果数组大小为零的话，说明是空节点了。

第二步：如果不为空，那么取后序数组最后一个元素作为节点元素。

第三步：找到后序数组最后一个元素在中序数组的位置，作为切割点

第四步：切割中序数组，切成中序左数组和中序右数组（顺序别搞反了，一定是先切中序数组）
切割点在后序数组的最后一个元素，就是用这个元素来切割中序数组的，所以必要先切割中序数组。

第五步：切割后序数组，切成后序左数组和后序右数组

第六步：递归处理左区间和右区间

上面第四和五步对于c语言的写法应该不一样，因为c语言写法是直接传入的两个数组和数组大小，所以切割是不需要分前后的

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
int linerSearch(int* arr,int arrSize,int key){
    int i;
    for(i=0;i<arrSize;i++){
        if(arr[i] == key){
            return i;
        }
    }
    return -1;
}

struct TreeNode* buildTree(int* inorder, int inorderSize, int* postorder, int postorderSize){
    //若中序遍历数组中没有元素，则返回NULL
    if(inorderSize == 0){
        return NULL;
    }
    //创建一个节点node，将 node->val 设置为后序数组中最后一个元素
    struct TreeNode* node= (struct TreeNode*)malloc(sizeof(struct TreeNode));
    node->val = postorder[postorderSize -1];

    //通过线性查找找到中间节点在中序数组中的位置
    int index = linerSearch(inorder,inorderSize,node->val);

    //左子树数组大小为index
    //右子树数组的大小为数组大小减index减1（减的1为中间节点）
    int rightSize = inorderSize - index -1;
    node ->left = buildTree(inorder,index,postorder,index);
    node ->right = buildTree(inorder + index+ 1,rightSize,postorder + index,rightSize);
    return node;

}

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

# 3、前序加中序

示例1：
输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]

示例 2:
输入: preorder = [-1], inorder = [-1]
输出: [-1]

1
2
3
4
5
6
7

思路和中序加后序一样，就是变成前序的第一个节点为中间节点，然后递归处理时，切割数组的范围也不一样而已

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
int linerSearch(int* arr,int arrSize,int key){
    int i;
    for(i=0;i<arrSize;i++){
        if(arr[i] == key){
            return i;
        }
    }
    return -1;
}

struct TreeNode* buildTree(int* preorder, int preorderSize, int* inorder, int inorderSize){
    //若中序遍历数组里没有元素，则返回NULL
    if(inorderSize == 0){
        return NULL;
    }
    //创建节点node，将node -> val置为前序遍历数组第一个数据
    struct TreeNode* node =(struct TreeNode*)malloc(sizeof(struct TreeNode));
    node ->val = preorder[0];

    //通过线性判断获取中间节点在中序遍历中的位置
    int index = linerSearch(inorder,inorderSize,node->val);

    //左子树数组大小为index
    //右子树数组的大小为数组大小减index减1（减的1为中间节点）
    int rightSize = inorderSize - index -1;
    node->left = buildTree(preorder + 1,index,inorder,index);
    node->right = buildTree(preorder + index+ 1,rightSize, inorder+index+1,rightSize);

    return node;

}

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
39

# 十八、合并二叉树

617. 合并二叉树 - 力扣（LeetCode） (opens new window)

# 1、题目

给你两棵二叉树： root1 和 root2 。

想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。

返回合并后的二叉树。

注意: 合并过程必须从两个树的根节点开始。
示例 1：
输入：root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
输出：[3,4,5,5,4,null,7]

示例 2：
输入：root1 = [1], root2 = [1,2]
输出：[2,2]
1
2
3
4
5
6
7
提示：

两棵树中的节点数目在范围 [0, 2000] 内

-104 <= Node.val <= 104

# 2、递归思路

同时递归处理处于同一位置的结点，让两个结点的数组相加
- ```
t1->val += t2->val;
```
  1

终止条件：

if (t1 == NULL) return t2; // 如果t1为空，合并之后就应该是t2
if (t2 == NULL) return t1; // 如果t2为空，合并之后就应该是t1

1
2

这里终止条件可以注意一下：
- 比方是遇到上面这种情况，一开始脑子没转过来，还在想为什么不用继续遍历下去，直接返回就可以了，其实在我们第一次出现有一方结点为 NULL 的情况时，我们是直接把不为 NULL 的结点返回，但是该结点的子结点又没有断开，所以也是一同返回的，所以直接返回不为NULL的结点就行

# 3、递归代码

struct TreeNode* mergeTrees(struct TreeNode* root1, struct TreeNode* root2){
    if(root1 == NULL ) return root2; // 如果t1为空，合并之后就应该是t2
    if(root2 == NULL ) return root1; // 如果t2为空，合并之后就应该是t1

    // 修改了t1的数值和结构
    root1->val +=root2->val;                                   //中
    root1 ->left = mergeTrees(root1->left,root2->left);        //左
    root1 ->right = mergeTrees(root1->right,root2->right);     //右
    return root1;
}

1
2
3
4
5
6
7
8
9
10

这道题，3种深度遍历方式都可以，就是改变语句顺序而已

# 4、迭代思路

创建两个队列，分别用来保存两个树的结点，只用一套指针，这样每次处理的都是相同位置的结点
判断结点是否有左右结点
- 如果都有左节点，就都将左节点加入对应队列
- 如果都有右节点，就都将左节点加入对应队列
- 如果root1没有左节点，root2有，那就将root2的左节点赋给root1（因为我们最后返回的是root1，所以要把节点给root1）
- 如果root1没有右节点，root2有，那就将root2的右节点赋给root1（因为我们最后返回的是root1，所以要把节点给root1）

# 5、迭代代码

struct TreeNode* mergeTrees(struct TreeNode* root1, struct TreeNode* root2){
    if(root1 == NULL) return root2;
    if(root2 == NULL) return root1;

    struct TreeNode* queue1[2000];
    struct TreeNode* queue2[2000];
    int front=0,rear =0;
    queue1[rear] = root1;
    queue2[rear] = root2;
    rear++;
    
   
    while(front !=rear){
        struct TreeNode* node1 = queue1[front];
        struct TreeNode* node2 = queue2[front];
        front++;

        //此时两个结点一定都不为空，val相加
        node1 ->val += node2 ->val;
        //如果两棵树左节点都不为空，加入队列
        if(node1 ->left != NULL && node2 -> left != NULL){
            queue1[rear] = node1 -> left;
            queue2[rear] = node2 -> left;
            rear++;
        }
        //如果两棵树右节点都不为空，加入队列
        if(node1 ->right != NULL && node2 -> right != NULL){
            queue1[rear] = node1 -> right;
            queue2[rear] = node2 -> right;
            rear++;
        }
        //当t1的左节点为空 ，t2左节点不为空，就赋值过去
         if(node1 ->left==NULL && node2 -> left != NULL){
            node1->left = node2 ->left;
        }
        //当t1的右节点为空 ，t2右节点不为空，就赋值过去
         if(node1 ->right==NULL && node2 -> right != NULL){
            node1->right = node2 ->right;
        }
    }
    return root1;

}

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
39
40
41
42
43

# 十九、二叉搜索树中的搜索

700. 二叉搜索树中的搜索 - 力扣（LeetCode） (opens new window)

# 1、题目

给定二叉搜索树（BST）的根节点 root 和一个整数值 val。

你需要在 BST 中找到节点值等于 val 的节点。返回以该节点为根的子树。如果节点不存在，则返回 null 。
示例 1:
输入：root = [4,2,7,1,3], val = 2
输出：[2,1,3]
1
2
3
示例 2:
输入：root = [4,2,7,1,3], val = 5
输出：[]
1
2
3
提示：

数中节点数在 [1, 5000] 范围内

1 <= Node.val <= 107

root 是二叉搜索树

1 <= val <= 107

# 2、普通写法

# 2.1 递归

//递归
struct TreeNode* searchBST(struct TreeNode* root, int val){
    //递归终止条件
    if(root==NULL||root->val == val) return root ;
    struct TreeNode* node = searchBST(root->left,val);
    if(node != NULL){
        return node;
    }

    node =  searchBST(root->right,val);
    if(node != NULL){
        return node;
    }

    return ;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# 2.2 迭代

//迭代
struct TreeNode* searchBST(struct TreeNode* root, int val){

    struct TreeNode* queue[5000];
    int rear=0,front=0;
    queue[rear++]=root;

    while(front != rear){
        int size = rear -front;
        for(int i=0;i<size;i++){
            struct TreeNode* node = queue[front++];
            if(node->val == val){
                return node;
            }
            if(node->left) queue[rear++] = node->left;
            if(node->right) queue[rear++] = node ->right;
        }
    }

    return NULL;
}

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

# 3、搜索二叉树性质

二叉搜索树是一个有序树：

若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；

若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；

它的左、右子树也分别为二叉搜索树

这就决定了，二叉搜索树，递归遍历和迭代遍历和普通二叉树都不一样。

# 4、搜索二叉树写法

# 4.1 递归

//搜索二叉树性质迭代
struct TreeNode* searchBST(struct TreeNode* root, int val){
    //递归终止条件
    if(root == NULL || root->val == val) return root;
    if(root->val > val){
        return searchBST(root->left,val);
    }
    else {
        return searchBST(root ->right,val);
    } 
}

1
2
3
4
5
6
7
8
9
10
11

# 4.2 迭代

//搜索二叉树性质迭代
struct TreeNode* searchBST(struct TreeNode* root, int val){
    while(root != NULL){
        if(root->val < val){
            root = root ->right;
        }
        else if(root->val > val){
            root = root ->left;
        }
        else return root; 
    }
    return NULL;
}

1
2
3
4
5
6
7
8
9
10
11
12
13

# 二十、验证二叉搜索树

98. 验证二叉搜索树 - 力扣（LeetCode） (opens new window)

代码随想录 (programmercarl.com) (opens new window)

# 1、题目

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效二叉搜索树定义如下：

节点的左子树只包含小于当前节点的数。节点的右子树只包含大于当前节点的数。所有左子树和右子树自身必须也是二叉搜索树。

示例 1：

输入：root = [2,1,3]
输出：true
1
2
3
4
示例 2：
输入：root = [5,1,4,null,null,3,6]
输出：false
解释：根节点的值是 5 ，但是右子节点的值是 4 。
1
2
3
提示：

树中节点数目范围在[1, 104] 内 -2^31 <= Node.val <= 2^31 - 1

❗❗注意：在里面还隐藏了一个关键的点就是，左子树所有节点小于中间节点，右子树所有节点大于中间节点，这一点非常容易被忽略

# 2、递归思路

根据搜索二叉树的性质，我们会发现如果我们使用中序遍历每个节点，那在这个遍历过程里每个节点的值应该都是递增的
定义一个全局变量，来记录上一个节点
中序遍历

//这个写法在leetcode提交时会错误，但是这种写法是没问题的
struct TreeNode* pre=NULL;
bool isValidBST(struct TreeNode* root){
    if(root == NULL) {
        return true;
    }
    bool left = isValidBST(root->left);  //左
    if(pre != NULL && pre->val >= root->val ) return false;  //中
    pre = root;
    bool right = isValidBST(root->right); //右
    return left && right;
}

1
2
3
4
5
6
7
8
9
10
11
12

判断 pre != NULL是为了第一次不判断

# 3、迭代法

中序遍历，记录上一个处理节点，与当前节点进行判断

bool isValidBST(struct TreeNode* root){
    if(root ==NULL) return true;
    struct TreeNode * stack[10000];
    int top = 0;
    struct TreeNode* lastnode=NULL;
    
    stack[top++] = root;
    while(top>0){
        struct TreeNode* node = stack[top-1];
        if(node != NULL){
            top--;
           if(node->right !=NULL) stack[top++] = node->right;
            stack[top++] = node;
            stack[top++] =NULL;
             if(node->left !=NULL) stack[top++] = node->left;
        }
        else {
            top--;
            node = stack[--top];
            if(lastnode != NULL && lastnode ->val >= node->val){
                return false;
            }
            lastnode = node;
        }
    }
    return true;
}

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

# 二十一、二叉搜索树的最小绝对差

# 1、题目

给你一个二叉搜索树的根节点 root ，返回树中任意两不同节点值之间的最小差值。

差值是一个正数，其数值等于两值之差的绝对值。
示例 1：
输入：root = [4,2,6,1,3]
输出：1
1
2
3
示例 2：
输入：root = [1,0,48,null,null,12,49]
输出：1
1
2
3
提示：

树中节点的数目范围是 [2, 104]

0 <= Node.val <= 10^5

# 2、递归

根据搜索二叉树的性质，我们会发现如果我们使用中序遍历每个节点，那在这个遍历过程里每个节点的值应该都是递增的
定义一个全局变量，来记录上一个节点
中序遍历

//递归
void dfs(struct TreeNode* root,int * pre,int * ans){
    if(root ==NULL) return ;
    dfs(root->left,pre,ans);
    if(*pre != -1 && root->val - (*pre) < *ans){
        *ans = root->val - (*pre);
    }
    *pre = root ->val;
    dfs(root->right,pre,ans);
}


int getMinimumDifference(struct TreeNode* root){
    //递归终止条件
    int ans =INT_MAX,pre=-1;
    dfs(root,&pre,&ans);
    return ans;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

# 3、迭代法

//迭代法
int getMinimumDifference(struct TreeNode* root){
    struct TreeNode* stack[10000];
    int top=0;
    struct TreeNode* lastnode = NULL;
    stack[top++]=root;
    int res = INT_MAX;

    while(top>0){
        struct TreeNode*node = stack[top-1];
        if(node != NULL){
            top--;
            if(node->right) stack[top++]= node->right;  //右
            stack[top++] = node;     //中
            stack[top++] =NULL;
            if(node->left) stack[top++]= node->left;  //左
        } else{
            top--;
            node = stack[--top];
            if(lastnode != NULL){
                if(node->val - lastnode ->val < res ){
                    res = node ->val - lastnode->val;
                }
            }
            lastnode =node;
        }
    }
    return res;
}

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

# 二十二、二叉搜索树中的众树

# 1、题目

给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有众数（即，出现频率最高的元素）。

如果树中有不止一个众数，可以按任意顺序返回。

假定 BST 满足如下定义：

结点左子树中所含节点的值小于等于当前节点的值结点右子树中所含节点的值大于等于当前节点的值左子树和右子树都是二叉搜索树
示例 1：
输入：root = [1,null,2,2]
输出：[2]
1
2
3
示例 2：
输入：root = [0]
输出：[0]c
1
2
3
提示：

树中节点的数目在范围 [1, 10^4] 内 -10^5 <= Node.val <= 10^5

进阶：你可以不使用额外的空间吗？（假设由递归产生的隐式调用栈的开销不被计算在内）

# 2、递归思路

首先我们一定能想到一个最朴素的做法：因为这棵树的中序遍历是一个有序的序列，所以我们可以先获得这棵树的中序遍历，然后从扫描这个中序遍历序列，然后用一个哈希表来统计每个数字出现的个数，这样就可以找到出现次数最多的数字。但是这样做的空间复杂度显然不是 O(1) 的，原因是哈希表和保存中序遍历序列的空间代价都是 O(n)。
首先，我们考虑在寻找出现次数最多的数时，不使用哈希表。这个优化是基于二叉搜索树中序遍历的性质：一棵二叉搜索树的中序遍历序列是一个非递减的有序序列。例如：

1
2
3
4
5

这样一颗二叉搜索树的中序遍历序列是{—1,0,0,1,2,2}。我们可以发现重复出现的数字一定是一个连续出现的，例如这里的0和2，它们都重复出现了，并且所有的0都集中在一个连续的段内，所有的2也集中在一个连续的段内。我们可以顺序扫描中序遍历序列，用base记录当前的数字，用count记录当前数字重复的次数，用maaCount 来维护已经扫描过的数当中出现最多的那个数字的出现次数，用ansuer数组记录出现的众数。每次扫描到一个新的元素:
- 首先更新base和count:
  - 如果该元素和base相等，那么count自增1;
  - 否则将base更新为当前数字，count复位为1。
- 然后更新 maxCount：
  - 如果count = maxCount，那么说明当前的这个数字(base)出现的次数等于当前众数出现的次数，将base加入answer数组; 如果count > maxCount，那么说明当前的这个数字(base)出现的次数大于当前众数出现的次数，因此，我们需要将maxCount更新为count，清空answer数组后将base加入ansuer数组。
我们可以把这个过程写成一个update函数。这样我们在寻找出现次数最多的数字的时候就可以省去一个哈希表带来的空间消耗。
然后，我们考虑不存储这个中序遍历序列。如果我们在递归进行中序遍历的过程中，访问当了某个点的时候直接使用上面的update 函数，就可以省去中序遍历序列的空间，代码如下。

# 3、递归代码

int* result;
int resSize;
int count,maxCount,base;

void update(int x){
    //如果当前节点的值等于上一个记录的值
    if(x == base){
        count++;  //计数加一
    }
    //如果不等于
    else{
        count = 1;  //重新计数
        base = x;  //修改记录值
    }

    //如果计数值等于最大计数值
    if(count == maxCount){
        result[resSize++] = base;
    }
    //如果计数值超过最大计数值
    if(count > maxCount){
        maxCount = count; //更新最大计数值
        resSize =0;  //清空记录数组
        result[resSize++] = base;//重新记录计数最大的节点
    }
}

void dfs(struct TreeNode* root){
    if(root ==NULL){
        return;
    }
    dfs(root->left);
    update(root->val);
    dfs(root->right);
}

int* findMode(struct TreeNode* root, int* returnSize) {
    base = maxCount = count =0;
    result = (int *)malloc(sizeof(int*)* 4001); 
    resSize =0;
    dfs(root);
    *returnSize = resSize;  //update函数里清空数组就是因为最后数组输出的大小是根据returnSzie决定的
    return result;

}

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
39
40
41
42
43
44
45

# 4、迭代

因为搜索二叉树的性质，我们直接中序遍历，判断每个节点与前一个结点是否相同。。。

int* findMode(struct TreeNode* root, int* returnSize) {
    int* result =(int*)malloc(sizeof(int)*10000); //写小了测试不过
    *returnSize =0;
    int count=0,maxCount=0,base=0;

    struct TreeNode* stack[10000];
    int top=0;
    stack[top++] = root;

    while(top>0){
        struct TreeNode* node = stack[top-1];
        if(node != NULL){
            top--;
            if(node ->left) stack[top++] =node->left;
            stack[top++] = node;
            stack[top++] = NULL;
            if(node ->right) stack[top++] =node->right;
        }
        else {
            top--;
            node = stack[--top];

            //如果当前节点的值等于上一个记录的值
            if(node ->val == base){
                count++;  //计数加一
            }
            //如果不等于
            else{
                count = 1;  //重新计数
                base = node ->val;  //修改记录值
            }

            //如果计数值等于最大计数值
            if(count == maxCount){
                result[(*returnSize)++] = base;
            }
            //如果计数值超过最大计数值
            if(count > maxCount){
                maxCount = count; //更新最大计数值
                (*returnSize) =0;  //清空记录数组
                result[(*returnSize)++] = base;//重新记录计数最大的节点
            }
        }
    }
    return result;
}

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
39
40
41
42
43
44
45
46

# 二十三、二叉树的最近公共祖先

# 1、题目

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
示例 1：
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。
1
2
3
4
示例 2：
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出：5
解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。
1
2
3
4
示例 3：

输入：root = [1,2], p = 1, q = 2
输出：1
1
2
3
4
提示：

树中节点数目在范围 [2, 10^5] 内。

-109 <= Node.val <= 109

所有 Node.val 互不相同。

p != q

p 和 q 均存在于给定的二叉树中。

# 2、自己写的递归

struct TreeNode* node=NULL;
bool traverse(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q){
    //递归终止条件
    if(root == q || root == p) {
        node = root;
        return true;
    }
    if(root ==NULL) return;

    bool node1 = traverse(root->left,p,q);
    bool node2 = traverse(root->right,p,q);
    if(node1 && node2 ) {
        node = root;
    }
    else if(node1 || node2) return true;

    return false;

}

struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) {
    traverse(root,p,q);
    return  node;

}

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

# 3、随想录递归

struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) {
    //递归终止条件
    if(root == p || root == q || root == NULL){
        return root;
    }

    struct TreeNode* left =lowestCommonAncestor(root->left,p,q);
    struct TreeNode* right =lowestCommonAncestor(root->right,p,q);
    //都不为空说明是最近公共祖先
    if(left != NULL && right != NULL) return root;
    //有一个为空，另一个不为空，返回不为空的节点，因为该节点为我们寻找的节点之一
    if(left == NULL && right != NULL) return right;
    else if(left != NULL && right == NULL) return left;
    
    else {
        return NULL;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

# 二十四、二叉搜索树的最近公共祖先

代码随想录 (programmercarl.com) (opens new window)

235. 二叉搜索树的最近公共祖先 - 力扣（LeetCode） (opens new window)

# 1、题目

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]
示例 1:
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6 
解释: 节点 2 和节点 8 的最近公共祖先是 6。
1
2
3
4
示例 2:

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输出: 2
解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。
1
2
3
4
5
说明:

所有节点的值都是唯一的。

p、q 为不同节点且均存在于给定的二叉搜索树中。

# 2、递归

根据二叉树的性质，可以看出我们遍历到的第一个处于[p,q] 或 [q,p] 区间的节点就是最近公共祖先

struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) {
    //递归终止条件
    if(root == NULL) return ;

    //root-> val 大于 [p,q]或 [q,p] ，就要向左遍历
    if(root->val > p->val && root->val > q->val){
        struct TreeNode* left = lowestCommonAncestor(root->left,p,q);
        if(left !=NULL){
            return left;
        }   
    }
    //root-> val 大于 [p,q]或 [q,p] ，就要向右遍历
    if(root->val < p->val && root->val < q->val){
        struct TreeNode* right = lowestCommonAncestor(root->right,p,q);
        if(right !=NULL){
            return right;
        }   
    }
    //除此之外就是在 [p,q]或 [q,p]范围内，那么我们第一个遍历到的处于范围内的就是我们要求的最近公共祖先

    return root;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

# 3、迭代

遍历树，根据搜索二叉树的性质，我们的遍历到的节点如果是在[p,q] 或 [q,p] 区间外，那么根据大小，遍历左右子树，如果节点的值在区间内，那么返回改节点，因为改节点就是搜索二叉树的最近公共祖先


struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) {
    while(root){
        if(root->val < p->val && root->val < q->val){
            root = root ->right;
        }
        else if(root->val > p->val && root->val > q->val){
            root = root ->left;
        }
        else {
            return root;
        }
    }
    return NULL;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# 二十五、二叉搜索树中的插入操作

# 1、题目

给定二叉搜索树（BST）的根节点 root 和要插入树中的值 value ，将值插入二叉搜索树。返回插入后二叉搜索树的根节点。输入数据保证，新值和原始二叉搜索树中的任意节点值都不同。

注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。你可以返回任意有效的结果。
示例 1：

输入：root = [4,2,7,1,3], val = 5
输出：[4,2,7,1,3,5]
1
2
3
4
解释：另一个满足题目要求可以通过的树是：
示例 2：
输入：root = [40,20,60,10,30,50,70], val = 25
输出：[40,20,60,10,30,50,70,null,null,25]
    
示例 3：
输入：root = [4,2,7,1,3,null,null,null,null,null,null], val = 5
输出：[4,2,7,1,3,5]
1
2
3
4
5
6
7
提示：
树中的节点数将在 [0, 10^4]的范围内。

-10^8 <= Node.val <= 10^8

所有值 Node.val 是独一无二的。

-10^8 <= val <= 10^8

保证 val 在原始BST中不存在。

# 2、思路

其实可以不考虑题目中提示所说的改变树的结构的插入方式。
如下演示视频中可以看出：只要按照二叉搜索树的规则去遍历，遇到空节点就插入节点就可以了。

701.二叉搜索树中的插入操作

例如插入元素10 ，需要找到末尾节点插入便可，一样的道理来插入元素15，插入元素0，插入元素6，需要调整二叉树的结构么？并不需要。。
只要遍历二叉搜索树，找到空节点插入元素就可以了，那么这道题其实就简单了。

# 3、递归

struct TreeNode* insertIntoBST(struct TreeNode* root, int val){
    if(root ==NULL){
        struct TreeNode* node=malloc(sizeof(struct TreeNode));
        node->val = val;
        //本来是只给val赋值了，没给左右节点赋值，然后就不通过，所以要给左右节点赋值
        node->left = node->right = NULL;
        return node;
    }

    if(root->val > val) root->left = insertIntoBST(root->left,val);
    if(root->val < val) root->right = insertIntoBST(root->right,val);

    return root;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14

# 4、迭代

struct TreeNode* insertIntoBST(struct TreeNode* root, int val){
   
   if( root == NULL){
       struct TreeNode* node=malloc(sizeof(struct TreeNode));
       node->val=val;
       node->left = node->right =NULL;
       return node;
   }

   struct TreeNode* cur =root;
   struct TreeNode* parent = root;
   while(cur != NULL){
       parent = cur;
       if(cur->val > val) cur = cur ->left;
       else cur = cur ->right;
   }

   struct TreeNode* node=malloc(sizeof(struct TreeNode));
   node->val = val;
   node->left = node->right =NULL;
   if(val < parent ->val) parent ->left = node;
    else parent->right = node;
    return root;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

# 二十六、删除二叉搜索树中的节点

450. 删除二叉搜索树中的节点 - 力扣（LeetCode） (opens new window)

代码随想录 (programmercarl.com) (opens new window)

# 1、题目

给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。

一般来说，删除节点可分为两个步骤：
首先找到需要删除的节点；

如果找到了，删除它。

示例 1:
输入：root = [5,3,6,2,4,null,7], key = 3
输出：[5,4,6,2,null,null,7]
解释：给定需要删除的节点值是 3，所以我们首先找到 3 这个节点，然后删除它。
一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。
另一个正确答案是 [5,2,6,null,4,null,7]。
1
2
3
4
5
示例 2:

输入: root = [5,3,6,2,4,null,7], key = 0
输出: [5,3,6,2,4,null,7]
解释: 二叉树不包含值为 0 的节点
1
2
3
4
5
示例 3:

输入: root = [], key = 0
输出: []
1
2
3
4
提示:

节点数的范围 [0, 10^4].

-10^5 <= Node.val <= 10^5

节点值唯一

root 是合法的二叉搜索树

-10^5 <= key <= 10^5

进阶：要求算法时间复杂度为 O(h)，h 为树的高度。

# 2、思路

这里就把二叉搜索树中删除节点遇到的情况都搞清楚。

有以下五种情况：
- 第一种情况：没找到删除的节点，遍历到空节点直接返回了
- 找到删除的节点
  - 第二种情况：左右孩子都为空（叶子节点），直接删除节点，返回NULL为根节点
  - 第三种情况：删除节点的左孩子为空，右孩子不为空，删除节点，右孩子补位，返回右孩子为根节点
  - 第四种情况：删除节点的右孩子为空，左孩子不为空，删除节点，左孩子补位，返回左孩子为根节点
  - 第五种情况：左右孩子节点都不为空，则将删除节点的左子树头结点（左孩子）放到删除节点的右子树的最左面节点的左孩子上，返回删除节点右孩子为新的根节点。
第五种情况有点难以理解，看下面动画：
动画中的二叉搜索树中，删除元素7，那么删除节点（元素7）的左孩子就是5，删除节点（元素7）的右子树的最左面节点是元素8。
将删除节点（元素7）的左孩子放到删除节点（元素7）的右子树的最左面节点（元素8）的左孩子上，就是把5为根节点的子树移到了8的左孩子的位置。
要删除的节点（元素7）的右孩子（元素9）为新的根节点。.
这样就完成删除元素7的逻辑，最好动手画一个图，尝试删除一个节点试试。

# 3、递归写法

struct TreeNode* deleteNode(struct TreeNode* root, int key){
    //递归终止条件
    //情况1：没找到输出的节点，遍历到空节点直接返回
    if(root == NULL) return NULL;

    if(root->val >key){
        root->left = deleteNode(root->left,key);
        return root;
    }
    if(root->val < key){
        root->right = deleteNode(root->right,key);
        return root;
    }

    //当找到要删除节点时
    if(root->val == key ){
        //情况2：左右孩子都为空，直接删除节点，返回NULL为根节点
        if(root->left == NULL && root->right == NULL ){
            return NULL;
        }
        //情况3：左孩子为空，右孩子不为空，删除节点，右孩子补位，返回右孩子为根节点
        else if(root->left == NULL && root->right != NULL ){
            return root->right;
        }
        //情况4：左孩子不为空，右孩子为空，删除节点，左孩子补位，返回右孩子为根节点
        else if(root->left != NULL && root->right == NULL ){
            return root->left;
        }
        else {
            //情况5：左右孩子节点都不为空，则将删除节点的左子树放到删除节点的右子树的最左面节点的左孩子的位置
            struct TreeNode* node = root-> right; //找右子树最左面的节点
            while(node->left !=NULL){
                node = node ->left;
            }
            node->left = root ->left;  //把要删除的节点（root）左子树放在node的左孩子的位置
            root = root->right; //返回旧root的右孩子最为新的root
            return root;
            }
        }
    return root;
}

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
39
40
41

# 二十七、修建二叉搜索树

代码随想录 (programmercarl.com) (opens new window)

669. 修剪二叉搜索树 - 力扣（LeetCode） (opens new window)

# 1、题目

给你二叉搜索树的根节点 root ，同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树，使得所有节点的值在[low, high]中。修剪树 不应该 改变保留在树中的元素的相对结构 (即，如果没有被移除，原有的父代子代关系都应当保留)。可以证明，存在 唯一的答案 。

所以结果应当返回修剪好的二叉搜索树的新的根节点。注意，根节点可能会根据给定的边界发生改变。

示例 1：
输入：root = [1,0,2], low = 1, high = 2
输出：[1,null,2]
1
2
示例 2：
输入：root = [3,0,4,null,2,null,null,1], low = 1, high = 3
输出：[3,2,null,1]
1
2
提示：

树中节点数在范围 [1, 10^4] 内

0 <= Node.val <= 10^4

树中每个节点的值都是唯一的

题目数据保证输入是一棵有效的二叉搜索树

0 <= low <= high <= 10^4

# 2、递归法

# 2.1 思路

前序遍历，处理不在目标区间内的节点
- 如果节点的值比区间小，那么删除当前节点，用节点右子节点补位
- 如果节点的值比区间大，那么删除当前节点，用节点左子节点补位

# 2.2 代码

struct TreeNode* trimBST(struct TreeNode* root, int low, int high){
    //递归终止条件
    if(root == NULL) return NULL;
    //寻找符合区间[low,high]的节点
    if(root->val < low){
        struct TreeNode* right= trimBST(root -> right,low,high);
        return right;
    }
    //寻找符合区间[low,high]的节点
    if(root->val > high){
        struct TreeNode* left = trimBST(root -> left,low,high);
        return left;
    }
    // root-> left 接入符合条件的左孩子
    root -> left =  trimBST(root -> left , low, high);
    // root-> right 接入符合条件的右孩子
    root -> right = trimBST(root -> right , low, high);
    return root;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

# 3、迭代法

# 3.1 思路

因为二叉搜索树的有序性，不需要使用栈模拟递归的过程。
在剪枝的时候，可以分为三步：
- 将root移动到[L, R] 范围内，注意是左闭右闭区间
- 剪枝左子树
- 剪枝右子树

# 3.2 代码

struct TreeNode* trimBST(struct TreeNode* root, int low, int high){
   if(!root) return NULL;

    //处理头节点，让root移动到[L,R] 范围内，注意是左闭右开
    while(root != NULL && (root->val <low || root->val >high)){
        if(root->val <low ) root = root->right; //小于low往右走
        else root= root->left; //大于high往左左
    }

    struct TreeNode* node = root;
    // 此时root已经在[L, R] 范围内，处理左孩子元素小于low的情况
    while(node != NULL){
        while(node ->left && node->left->val <low){
            node->left = node->left->right;
        }
        node = node->left;
    }
    node = root;

    // 此时root已经在[L, R] 范围内，处理右孩子大于R的情况
    while (node != NULL) {
        while (node->right && node->right->val > high) {
            node->right = node->right->left;
        }
        node = node->right;
    }
    return root;

}

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

这里在处理元素时循环里面又用了一层循环是因为有可能补位后的左右节点依旧不在范围内，所以要循环

# 二十八、将有序数组转换为二叉搜索树

# 1、题目

给你一个整数数组 nums ，其中元素已经按升序排列，请你将其转换为一棵高度平衡二叉搜索树。

高度平衡二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

示例 1：
输入：nums = [-10,-3,0,5,9]
输出：[0,-3,9,-10,null,5]
解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：
1
2
3
示例 2：
输入：nums = [1,3]
输出：[3,1]
解释：[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。
1
2
3
提示：

1 <= nums.length <= 104

-104 <= nums[i] <= 104

nums 按 严格递增 顺序排列

# 2、递归

其实数组构造二叉树，构成平衡树是自然而然的事情，因为大家默认都是从数组中间位置取值作为节点元素，一般不会随机取。所以想构成不平衡的二叉树是自找麻烦。
本质就是寻找分割点，分割点作为当前节点，然后递归左区间和右区间。

struct TreeNode* traversal(int* nums, int left, int right) {
    if (left > right) 
        return NULL;
    int mid = left + ((right - left) / 2);
    struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->val = nums[mid];
    root->left = traversal(nums, left, mid - 1);
    root->right = traversal(nums, mid + 1, right);
    return root;
}

struct TreeNode* sortedArrayToBST(int* nums, int numsSize) {
    struct TreeNode* root = traversal(nums, 0, numsSize - 1);
    return root;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

首先取数组中间元素的位置，不难写出int mid = (left + right) / 2;，这么写其实有一个问题，就是数值越界，例如left和right都是最大int，这么操作就越界了，在二分法 (opens new window) (opens new window)中尤其需要注意！

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

int sum=0;
struct TreeNode* convertBST(struct TreeNode* root){
    //反向中序遍历（右中左）
    //递归终止条件
    if(root== NULL){
        return ;
    }
    if(root ->right) convertBST(root ->right); //右
    sum += root -> val;     //处理节点    中
    root -> val = sum;
    if(root -> left) convertBST(root -> left); //左

    return root;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

# 二十九、将二叉搜索树装换为累加树

代码随想录 (programmercarl.com) (opens new window)

538. 把二叉搜索树转换为累加树 - 力扣（LeetCode） (opens new window)

# 1、题目

给出二叉搜索树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。

提醒一下，二叉搜索树满足下列约束条件：

节点的左子树仅包含键小于节点键的节点。节点的右子树仅包含键大于节点键的节点。左右子树也必须是二叉搜索树。注意：本题和 1038: https://leetcode-cn.com/problems/binary-search-tree-to-greater-sum-tree/ 相同
示例 1：
输入：[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
输出：[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]

示例 2：
输入：root = [0,null,1]
输出：[1,null,1]

示例 3：
输入：root = [1,0,2]
输出：[3,3,2]

示例 4：
输入：root = [3,2,4,1]
输出：[7,9,4,10]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
提示：
树中的节点数介于 0 和 10^4 之间。

每个节点的值介于 -10^4 和 10^4 之间。

树中的所有值 互不相同 。

给定的树为二叉搜索树。

# 2、思路

这道题看起来难其实是比较简单的，我们知道中序遍历二叉搜索树就能得到一个升序数组，而我们这道题要使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。
所以我们可以反序中序遍历，这样遍历的就是一个降序数组

# 3、递归

int sum;
struct TreeNode*dfs(struct TreeNode* root){
    if(root!=NULL){
        dfs(root->right);
        sum+= root->val;
        root ->val =sum;
        dfs(root->left);
    }
    return root;
}

struct TreeNode* convertBST(struct TreeNode* root){
    sum =0;
    dfs(root);
    return root;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# 4、迭代

struct TreeNode* convertBST(struct TreeNode* root){
    if(root ==NULL){
        return NULL;
    }
    struct TreeNode * stack[10000];
    int top;
    int sum=0;
    stack[top++]=root;
    while(top>0){
        struct TreeNode* node = stack[top -1];
        if(node !=NULL){
            top--; //取出栈顶元素
            //栈操作，我们要反序进行中序遍历，所以要先进入左节点
            if(node->left){
            stack[top++] = node->left;
            }
            stack[top++] = node;
            stack[top++] = NULL;      //加入NULL标志
            if(node->right){
            stack[top++] = node->right;
            }      
        }
        //如果为NULL，说明是要处理的元素
        else{
            top--;//弹出NULL指针
            node = stack[--top];
            sum += node -> val;
            node ->val = sum;
        }
    }
    return root;
}

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

编辑

上次更新: 2023/09/13, 12:29:52

← 二叉树(中) 回溯算法→