二叉树（三）

本文为学习代码随想录时所做的笔记，仅供学习参考，不做任何商业用途，若有侵权，请联系删除。

合并二叉树

617. 合并二叉树 - 力扣（LeetCode）

  1. 确定递归函数的参数和返回值

    1
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2)

  2. 确定终止条件

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

  3. 确定单层递归的逻辑

    1
    2
    3
    t1->left = mergeTrees(t1->left, t2->left);
    t1->right = mergeTrees(t1->right, t2->right);
    return t1;

前序遍历

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        if (t1 == NULL) return t2; // 如果t1为空，合并之后就应该是t2
        if (t2 == NULL) return t1; // 如果t2为空，合并之后就应该是t1
        // 修改了t1的数值和结构
        t1->val += t2->val;                             // 中
        t1->left = mergeTrees(t1->left, t2->left);      // 左
        t1->right = mergeTrees(t1->right, t2->right);   // 右
        return t1;
    }
};

中序遍历

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        if (t1 == NULL) return t2; // 如果t1为空，合并之后就应该是t2
        if (t2 == NULL) return t1; // 如果t2为空，合并之后就应该是t1
        // 修改了t1的数值和结构
        t1->left = mergeTrees(t1->left, t2->left);      // 左
        t1->val += t2->val;                             // 中
        t1->right = mergeTrees(t1->right, t2->right);   // 右
        return t1;
    }
};

后序遍历

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        if (t1 == NULL) return t2; // 如果t1为空，合并之后就应该是t2
        if (t2 == NULL) return t1; // 如果t2为空，合并之后就应该是t1
        // 修改了t1的数值和结构
        t1->left = mergeTrees(t1->left, t2->left);      // 左
        t1->right = mergeTrees(t1->right, t2->right);   // 右
        t1->val += t2->val;                             // 中
        return t1;
    }
};

二叉树中的搜索

700. 二叉搜索树中的搜索 - 力扣（LeetCode）

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

  • 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
  • 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
  • 它的左、右子树也分别为二叉搜索树

递归法

  1. 确定递归函数的参数和返回值

    1
    TreeNode* searchBST(TreeNode* root, int val)

  2. 确定终止条件

    1
    if (root == NULL || root->val == val) return root;

  3. 确定单层递归的逻辑

    1
    2
    3
    4
    TreeNode* result = NULL;
    if (root->val > val) result = searchBST(root->left, val);
    if (root->val < val) result = searchBST(root->right, val);
    return result;
1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        if (root == NULL || root->val == val) return root;
        TreeNode* result = NULL;
        if (root->val > val) result = searchBST(root->left, val);
        if (root->val < val) result = searchBST(root->right, val);
        return result;
    }
};

迭代法

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        while (root != NULL) {
            if (root->val > val) root = root->left;
            else if (root->val < val) root = root->right;
            else return root;
        }
        return NULL;
    }
};

验证二叉搜索树

98. 验证二叉搜索树 - 力扣（LeetCode）

递归法

可以递归中序遍历将二叉搜索树转变成一个数组，代码如下：

1
2
3
4
5
6
7
vector<int> vec;
void traversal(TreeNode* root) {
    if (root == NULL) return;
    traversal(root->left);
    vec.push_back(root->val); // 将二叉搜索树转换为有序数组
    traversal(root->right);
}

然后只要比较一下，这个数组是否是有序的，注意二叉搜索树中不能有重复元素。

1
2
3
4
5
6
traversal(root);
for (int i = 1; i < vec.size(); i++) {
    // 注意要小于等于，搜索树里不能有相同元素
    if (vec[i] <= vec[i - 1]) return false;
}
return true;

整体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
private:
    vector<int> vec;
    void traversal(TreeNode* root) {
        if (root == NULL) return;
        traversal(root->left);
        vec.push_back(root->val); // 将二叉搜索树转换为有序数组
        traversal(root->right);
    }
public:
    bool isValidBST(TreeNode* root) {
        vec.clear(); // 不加这句在leetcode上也可以过，但最好加上
        traversal(root);
        for (int i = 1; i < vec.size(); i++) {
            // 注意要小于等于，搜索树里不能有相同元素
            if (vec[i] <= vec[i - 1]) return false;
        }
        return true;
    }
};

直接比较

  • 确定递归函数，返回值以及参数

    1
    2
    long long maxVal = LONG_MIN; // 因为后台测试数据中有int最小值
    bool isValidBST(TreeNode* root)

  • 确定终止条件

    1
    if (root == NULL) return true;

  • 确定单层递归的逻辑

    1
    2
    3
    4
    5
    6
    7
    8
    bool left = isValidBST(root->left);         // 左

    // 中序遍历，验证遍历的元素是不是从小到大
    if (maxVal < root->val) maxVal = root->val; // 中
    else return false;

    bool right = isValidBST(root->right);       // 右
    return left && right;

整体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    TreeNode* pre = NULL; // 用来记录前一个节点
    bool isValidBST(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;
    }
};

二叉搜索树的最小绝对差

530. 二叉搜索树的最小绝对差 - 力扣（LeetCode）

递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
private:
vector<int> vec;
void traversal(TreeNode* root) {
    if (root == NULL) return;
    traversal(root->left);
    vec.push_back(root->val); // 将二叉搜索树转换为有序数组
    traversal(root->right);
}
public:
    int getMinimumDifference(TreeNode* root) {
        vec.clear();
        traversal(root);
        if (vec.size() < 2) return 0;
        int result = INT_MAX;
        for (int i = 1; i < vec.size(); i++) { // 统计有序数组的最小差值
            result = min(result, vec[i] - vec[i-1]);
        }
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
private:
int result = INT_MAX;
TreeNode* pre = NULL;
void traversal(TreeNode* cur) {
    if (cur == NULL) return;
    traversal(cur->left);   // 左
    if (pre != NULL){       // 中
        result = min(result, cur->val - pre->val);
    }
    pre = cur; // 记录前一个
    traversal(cur->right);  // 右
}
public:
    int getMinimumDifference(TreeNode* root) {
        traversal(root);
        return result;
    }
};

二叉搜索树中的众数

501. 二叉搜索树中的众数 - 力扣（LeetCode）

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
class Solution {
private:
    int maxCount = 0; // 最大频率
    int count = 0; // 统计频率
    TreeNode* pre = NULL;
    vector<int> result;
    void searchBST(TreeNode* cur) {
        if (cur == NULL) return ;

        searchBST(cur->left);       // 左
                                    // 中
        if (pre == NULL) { // 第一个节点
            count = 1;
        } else if (pre->val == cur->val) { // 与前一个节点数值相同
            count++;
        } else { // 与前一个节点数值不同
            count = 1;
        }
        pre = cur; // 更新上一个节点

        if (count == maxCount) { // 如果和最大值相同，放进result中
            result.push_back(cur->val);
        }

        if (count > maxCount) { // 如果计数大于最大值频率
            maxCount = count;   // 更新最大频率
            result.clear();     // 很关键的一步，不要忘记清空result，之前result里的元素都失效了
            result.push_back(cur->val);
        }

        searchBST(cur->right);      // 右
        return ;
    }

public:
    vector<int> findMode(TreeNode* root) {
        count = 0;
        maxCount = 0;
        TreeNode* pre = NULL; // 记录前一个节点
        result.clear();

        searchBST(root);
        return result;
    }
};

二叉树的最近公共祖先

236. 二叉树的最近公共祖先 - 力扣（LeetCode）

  • 确定递归函数的返回值以及参数

    1
    2
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q)

  • 确定终止条件

    1
    if (root == q || root == p || root == NULL) return root;

  • 确定单层递归逻辑

    1
    2
    3
    left = 递归函数(root->left);  // 左
    right = 递归函数(root->right); // 右
    left与right的逻辑处理;         // 中 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root == q || root == p || root == NULL) return root;
        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        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  { //  (left == NULL && right == NULL)
            return NULL;
        }

    }
};

二叉搜索树的最近公共祖先

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

当我们从上向下去递归遍历，第一次遇到 cur节点是数值在[p, q]区间中，那么cur就是 p和q的最近公共祖先。

递归法

  • 确定递归函数返回值以及参数

    1
    TreeNode* traversal(TreeNode* cur, TreeNode* p, TreeNode* q)

  • 确定终止条件

    1
    if (cur == NULL) return cur;

  • 确定单层递归逻辑

    1
    2
    3
    4
    5
    6
    if (cur->val > p->val && cur->val > q->val) {
        TreeNode* left = traversal(cur->left, p, q);
        if (left != NULL) {
            return left;
        }
    }
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
class Solution {
private:
    TreeNode* traversal(TreeNode* cur, TreeNode* p, TreeNode* q) {
        if (cur == NULL) return cur;
                                                        // 中
        if (cur->val > p->val && cur->val > q->val) {   // 左
            TreeNode* left = traversal(cur->left, p, q);
            if (left != NULL) {
                return left;
            }
        }

        if (cur->val < p->val && cur->val < q->val) {   // 右
            TreeNode* right = traversal(cur->right, p, q);
            if (right != NULL) {
                return right;
            }
        }
        return cur;
    }
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        return traversal(root, p, q);
    }
};

二叉搜索树中的插入操作

701. 二叉搜索树中的插入操作 - 力扣（LeetCode）

  • 确定递归函数参数以及返回值

    1
    TreeNode* insertIntoBST(TreeNode* root, int val)

  • 确定终止条件

    1
    2
    3
    4
    if (root == NULL) {
        TreeNode* node = new TreeNode(val);
        return node;
    }

  • 确定单层递归的逻辑

    1
    2
    3
    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
class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        if (root == NULL) {
            TreeNode* node = new TreeNode(val);
            return node;
        }
        if (root->val > val) root->left = insertIntoBST(root->left, val);
        if (root->val < val) root->right = insertIntoBST(root->right, val);
        return root;
    }
};

删除二叉搜索书中的节点

450. 删除二叉搜索树中的节点 - 力扣（Leetcode）

  • 确定递归函数参数以及返回值

    1
    TreeNode* deleteNode(TreeNode* root, int key)

  • 确定终止条件

    1
    if (root == nullptr) return root;

  • 确定单层递归的逻辑

    • 第一种情况：没找到删除的节点，遍历到空节点直接返回了

    • 找到删除的节点

      • 第二种情况：左右孩子都为空（叶子节点），直接删除节点， 返回NULL为根节点

      • 第三种情况：删除节点的左孩子为空，右孩子不为空，删除节点，右孩子补位，返回右孩子为根节点

      • 第四种情况：删除节点的右孩子为空，左孩子不为空，删除节点，左孩子补位，返回左孩子为根节点

      • 第五种情况：左右孩子节点都不为空，则将删除节点的左子树头结点（左孩子）放到删除节点的右子树的最左面节点的左孩子上，返回删除节点右孩子为新的根节点。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    if (root->val == key) {
        // 第二种情况：左右孩子都为空（叶子节点），直接删除节点， 返回NULL为根节点
        // 第三种情况：其左孩子为空，右孩子不为空，删除节点，右孩子补位 ，返回右孩子为根节点
        if (root->left == nullptr) return root->right;
        // 第四种情况：其右孩子为空，左孩子不为空，删除节点，左孩子补位，返回左孩子为根节点
        else if (root->right == nullptr) return root->left;
        // 第五种情况：左右孩子节点都不为空，则将删除节点的左子树放到删除节点的右子树的最左面节点的左孩子的位置
        // 并返回删除节点右孩子为新的根节点。
        else {
            TreeNode* cur = root->right; // 找右子树最左面的节点
            while(cur->left != nullptr) {
                cur = cur->left;
            }
            cur->left = root->left; // 把要删除的节点（root）左子树放在cur的左孩子的位置
            TreeNode* tmp = root;   // 把root节点保存一下，下面来删除
            root = root->right;     // 返回旧root的右孩子作为新root
            delete tmp;             // 释放节点内存（这里不写也可以，但C++最好手动释放一下吧）
            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
42
43
44
class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        if (root == nullptr) return root; // 第一种情况：没找到删除的节点，遍历到空节点直接返回了
        if (root->val == key) {
            // 第二种情况：左右孩子都为空（叶子节点），直接删除节点， 返回NULL为根节点
            if (root->left == nullptr && root->right == nullptr) {
                ///! 内存释放
                delete root;
                return nullptr;
            }
            // 第三种情况：其左孩子为空，右孩子不为空，删除节点，右孩子补位 ，返回右孩子为根节点
            else if (root->left == nullptr) {
                auto retNode = root->right;
                ///! 内存释放
                delete root;
                return retNode;
            }
            // 第四种情况：其右孩子为空，左孩子不为空，删除节点，左孩子补位，返回左孩子为根节点
            else if (root->right == nullptr) {
                auto retNode = root->left;
                ///! 内存释放
                delete root;
                return retNode;
            }
            // 第五种情况：左右孩子节点都不为空，则将删除节点的左子树放到删除节点的右子树的最左面节点的左孩子的位置
            // 并返回删除节点右孩子为新的根节点。
            else {
                TreeNode* cur = root->right; // 找右子树最左面的节点
                while(cur->left != nullptr) {
                    cur = cur->left;
                }
                cur->left = root->left; // 把要删除的节点（root）左子树放在cur的左孩子的位置
                TreeNode* tmp = root;   // 把root节点保存一下，下面来删除
                root = root->right;     // 返回旧root的右孩子作为新root
                delete tmp;             // 释放节点内存（这里不写也可以，但C++最好手动释放一下吧）
                return root;
            }
        }
        if (root->val > key) root->left = deleteNode(root->left, key);
        if (root->val < key) root->right = deleteNode(root->right, key);
        return root;
    }
};

普通二叉树的删除

代码中目标节点（要删除的节点）被操作了两次：

  • 第一次是和目标节点的右子树最左面节点交换。
  • 第二次直接被NULL覆盖了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        if (root == nullptr) return root;
        if (root->val == key) {
            if (root->right == nullptr) { // 这里第二次操作目标值：最终删除的作用
                return root->left;
            }
            TreeNode *cur = root->right;
            while (cur->left) {
                cur = cur->left;
            }
            swap(root->val, cur->val); // 这里第一次操作目标值：交换目标值其右子树最左面节点。
        }
        root->left = deleteNode(root->left, key);
        root->right = deleteNode(root->right, key);
        return root;
    }
};

修剪二叉搜索树

669. 修剪二叉搜索树 - 力扣（Leetcode）

递归法

  • 确定递归函数的参数以及返回值

    1
    TreeNode* trimBST(TreeNode* root, int low, int high)

  • 确定终止条件

    1
    if (root == nullptr ) return nullptr;

  • 确定单层递归的逻辑

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    if (root->val < low) {
        TreeNode* right = trimBST(root->right, low, high); // 寻找符合区间[low, high]的节点
        return right;
    }

    if (root->val > high) {
        TreeNode* left = trimBST(root->left, low, high); // 寻找符合区间[low, high]的节点
        return left;
    }

    root->left = trimBST(root->left, low, high); // root->left接入符合条件的左孩子
    root->right = trimBST(root->right, low, high); // root->right接入符合条件的右孩子
    return root;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    TreeNode* trimBST(TreeNode* root, int low, int high) {
        if (root == nullptr ) return nullptr;
        if (root->val < low) {
            TreeNode* right = trimBST(root->right, low, high); // 寻找符合区间[low, high]的节点
            return right;
        }
        if (root->val > high) {
            TreeNode* left = trimBST(root->left, low, high); // 寻找符合区间[low, high]的节点
            return left;
        }
        root->left = trimBST(root->left, low, high); // root->left接入符合条件的左孩子
        root->right = trimBST(root->right, low, high); // root->right接入符合条件的右孩子
        return root;
    }
};

将有序数组转换为二叉搜索树

108. 将有序数组转换为二叉搜索树 - 力扣（Leetcode）

本质就是寻找分割点，分割点作为当前节点，然后递归左区间和右区间

递归

  • 确定递归函数返回值及其参数

    1
    2
    // 左闭右闭区间[left, right]
    TreeNode* traversal(vector<int>& nums, int left, int right)

  • 确定递归终止条件

    1
    if (left > right) return nullptr;

  • 确定单层递归逻辑

    1
    2
    3
    4
    5
    int mid = left + ((right - left) / 2);
    TreeNode* root = new TreeNode(nums[mid]);
    root->left = traversal(nums, left, mid - 1);
    root->right = traversal(nums, mid + 1, right);
    return root;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
private:
    TreeNode* traversal(vector<int>& nums, int left, int right) {
        if (left > right) return nullptr;
        int mid = left + ((right - left) / 2);
        TreeNode* root = new TreeNode(nums[mid]);
        root->left = traversal(nums, left, mid - 1);
        root->right = traversal(nums, mid + 1, right);
        return root;
    }
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        TreeNode* root = traversal(nums, 0, nums.size() - 1);
        return root;
    }
};

把二叉树搜索树转换为累加树

538. 把二叉搜索树转换为累加树 - 力扣（Leetcode）

递归

从树中可以看出累加的顺序是右中左，所以我们需要反中序遍历这个二叉树，然后顺序累加就可以了

  • 递归函数以及其返回值

    1
    2
    int pre = 0; // 记录前一个节点的数值
    void traversal(TreeNode* cur)

  • 确定终止条件

    1
    if (cur == nullptr) return;

  • 确定单层递归逻辑

    1
    2
    3
    4
    traversal(cur->right);  // 右
    cur->val += pre;        // 中
    pre = cur->val;
    traversal(cur->left);   // 左
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
private:
    int pre = 0; // 记录前一个节点的数值
    void traversal(TreeNode* cur) { // 右中左遍历
        if (cur == NULL) return;
        traversal(cur->right);
        cur->val += pre;
        pre = cur->val;
        traversal(cur->left);
    }
public:
    TreeNode* convertBST(TreeNode* root) {
        pre = 0;
        traversal(root);
        return root;
    }
};

回溯算法

123

算法
#数据结构 #二叉树
二叉树（三）
https://www.spacezxy.top/2022/10/25/Algorithm/algorithm-8/
作者
Xavier ZXY
发布于
2022年10月25日
许可协议