二叉树专题训练三

5 minute read

5/9

T450 删除二叉搜索树中的节点

摘录《代码随想录》情况分析：

有以下五种情况：

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

找到删除的节点

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

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

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

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

这一题难在多情况分析，第五个情况需要静下心来理解，可参考题解中的动画复习。

class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {

        // 第一种情况：没找到删除节点
        if (root == nullptr) return root;

        // 找到目标节点
        if (root->val == key) {

            // 第二种情况：叶子节点
            if (root->left == nullptr && root->right == nullptr) {
                delete root;
                return nullptr;
            }

            // 第三种情况：左空右不空
            else if (root->left == nullptr) {
                TreeNode* retNode = root->right;
                delete root;
                return retNode;
            }

            // 第四种情况：右空左不空
            else if (root->right == nullptr) {
                TreeNode* retNode = root->left;
                delete root;
                return retNode;
            }

            // 第五种情况：左右孩子都不为空
            else {

                // 找右子树最左节点
                TreeNode* cur = root->right;

                while (cur->left != nullptr) {
                    cur = cur->left;
                }

                // 将原左子树接过去
                cur->left = root->left;

                TreeNode* tmp = root;

                // 新根节点
                root = root->right;

                delete tmp;

                return root;
            }
        }

        // 去左子树删除
        if (root->val > key) {
            root->left = deleteNode(root->left, key);
        }

        // 去右子树删除
        if (root->val < key) {
            root->right = deleteNode(root->right, key);
        }

        return root;
    }
};

T701 二叉搜索树中的插入操作

本题不必重构二叉树，巧妙插入即可，递归法更易理解。

class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {

        // 找到空位置，直接插入
        if (root == nullptr) {
            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;
    }
};

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

和昨天题目类似，稍有变换。

BST 的性质：

若当前节点值同时大于 p、q，则最近公共祖先一定在左子树
若当前节点值同时小于 p、q，则最近公共祖先一定在右子树
否则当前节点就是最近公共祖先

class Solution {
private:

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

        if (cur == nullptr) return cur;

        // 去左子树
        if (cur->val > p->val && cur->val > q->val) {

            TreeNode* left = traversal(cur->left, p, q);

            if (left != nullptr) {
                return left;
            }
        }

        // 去右子树
        if (cur->val < p->val && cur->val < q->val) {

            TreeNode* right = traversal(cur->right, p, q);

            if (right != nullptr) {
                return right;
            }
        }

        // 当前节点位于中间
        return cur;
    }

public:

    TreeNode* lowestCommonAncestor(TreeNode* root,
                                   TreeNode* p,
                                   TreeNode* q) {

        return traversal(root, p, q);
    }
};

5/8

T236 二叉树的最近公共祖先

关键：

在递归函数有返回值的情况下：

如果要搜索一条边，递归函数返回值不为空的时候，立刻返回
如果搜索整个树，则直接用 left、right 接住返回值，因为后序处理中间节点时还需要逻辑判断

class Solution {
public:

    TreeNode* lowestCommonAncestor(TreeNode* root,
                                   TreeNode* p,
                                   TreeNode* q) {

        // 找到目标节点或空节点
        if (root == p || root == q || root == nullptr) {
            return root;
        }

        // 左
        TreeNode* left = lowestCommonAncestor(root->left, p, q);

        // 右
        TreeNode* right = lowestCommonAncestor(root->right, p, q);

        // 左右都找到
        if (left != nullptr && right != nullptr) {
            return root;
        }

        // 只有右边找到
        if (left == nullptr && right != nullptr) {
            return right;
        }

        // 只有左边找到
        else if (left != nullptr && right == nullptr) {
            return left;
        }

        // 都没找到
        else {
            return nullptr;
        }
    }
};

5/7

T501 二叉搜索树中的众数【重要题目】

1、暴力做法

直接遍历统计频率。

class Solution {
private:

    void searchBST(TreeNode* cur,
                   unordered_map<int, int>& map) {

        if (cur == nullptr) return;

        map[cur->val]++;

        searchBST(cur->left, map);
        searchBST(cur->right, map);
    }

    static bool cmp(const pair<int, int>& a,
                    const pair<int, int>& b) {

        return a.second > b.second;
    }

public:

    vector<int> findMode(TreeNode* root) {

        unordered_map<int, int> map;

        vector<int> result;

        if (root == nullptr) return result;

        searchBST(root, map);

        vector<pair<int, int>> vec(map.begin(), map.end());

        sort(vec.begin(), vec.end(), cmp);

        result.push_back(vec[0].first);

        for (int i = 1; i < vec.size(); i++) {

            if (vec[i].second == vec[0].second) {
                result.push_back(vec[i].first);
            }

            else {
                break;
            }
        }

        return result;
    }
};

2、BST 中序遍历优化

经典套路：

二叉搜索树的中序遍历是有序的。

注：

result.clear() 非常重要。

class Solution {
private:

    int maxCount = 0;

    int count = 0;

    TreeNode* pre = nullptr;

    vector<int> result;

    void searchBST(TreeNode* cur) {

        if (cur == nullptr) return;

        // 左
        searchBST(cur->left);

        // 中

        if (pre == nullptr) {

            count = 1;
        }

        else if (pre->val == cur->val) {

            count++;
        }

        else {

            count = 1;
        }

        pre = cur;

        // 与最大频率相同
        if (count == maxCount) {

            result.push_back(cur->val);
        }

        // 出现更大频率
        if (count > maxCount) {

            maxCount = count;

            // 很关键
            result.clear();

            result.push_back(cur->val);
        }

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

public:

    vector<int> findMode(TreeNode* root) {

        count = 0;
        maxCount = 0;
        pre = nullptr;

        result.clear();

        searchBST(root);

        return result;
    }
};

3、BST 中序遍历有序性的严格证明（数学归纳法）

设：

T 为 BST
root 为根节点
L 为左子树
R 为右子树

BST 定义：

∀x ∈ L :
x ≤ root

∀y ∈ R :
y ≥ root

且：

L, R 也均为 BST

定义：

In(T)

表示 T 的中序遍历序列。

则：

In(T)
=
In(L) ⊕ [root] ⊕ In(R)

其中：

⊕

表示序列拼接。

证明：

∀ BST T :

In(T) 为非递减序列

数学归纳法

【1】Base Case

|T| = 0 :

In(T) = []

有序

|T| = 1 :

In(T) = [root]

有序

【2】Induction Hypothesis

假设：

∀ |T| < n :

In(T) 有序

即：

In(L) 有序
In(R) 有序

【3】Induction Step

对于：

|T| = n

根据 BST 定义：

∀a ∈ In(L) :
a ≤ root

∀b ∈ In(R) :
b ≥ root

根据归纳假设：

In(L) :
a1 ≤ a2 ≤ ... ≤ ak

In(R) :
b1 ≤ b2 ≤ ... ≤ bm

又：

ak ≤ root ≤ b1

因此：

a1 ≤ a2 ≤ ... ≤ ak
≤ root ≤
b1 ≤ b2 ≤ ... ≤ bm

即：

In(T)
=
In(L) ⊕ [root] ⊕ In(R)

为非递减序列。

∴

∀ BST T :

In(T) 单调非递减

证毕。

5/5

T530 二叉搜索树的最小绝对差

1、核心思想

对于每一个节点：

和它最小差值的节点，必然为：

左子树中的最大值
右子树中的最小值

即：

左子节点的右右右...直到最右
右子节点的左左左...直到最左

注意：

最右/最左不一定是叶子节点。

反例：

2、本质

本质是寻找：

左子树最大值
右子树最小值

int getPredecessor(TreeNode* root) {

    root = root->left;

    while (root->right) {
        root = root->right;
    }

    return root->val;
}

int getSuccessor(TreeNode* root) {

    root = root->right;

    while (root->left) {
        root = root->left;
    }

    return root->val;
}

3、重要思想

没有现成递归需求时：

为了遍历所有节点，需要自己构造 DFS。

class Solution {
private:

    int res = INT_MAX;

    int getPredecessor(TreeNode* root) {

        root = root->left;

        while (root->right) {
            root = root->right;
        }

        return root->val;
    }

    int getSuccessor(TreeNode* root) {

        root = root->right;

        while (root->left) {
            root = root->left;
        }

        return root->val;
    }

    void dfs(TreeNode* root) {

        if (!root) return;

        // 和前驱比较
        if (root->left) {

            int pre = getPredecessor(root);

            res = min(res, root->val - pre);
        }

        // 和后继比较
        if (root->right) {

            int suc = getSuccessor(root);

            res = min(res, suc - root->val);
        }

        dfs(root->left);
        dfs(root->right);
    }

public:

    int getMinimumDifference(TreeNode* root) {

        dfs(root);

        return res;
    }
};

5/4

【复习教程中递归的通用范式】

1、确定递归函数参数和返回类型

参数：

二叉树根节点
一个计数器 count

count 用于统计路径和。

什么时候需要返回值？

1、搜索整棵树且不处理递归返回值
→ 不需要返回值

2、搜索整棵树且需要处理递归返回值
→ 需要返回值

3、搜索一条符合条件路径
→ 必须返回值
因为找到后需要立刻返回

2、确定终止条件

核心思想：

不要累加。

使用：

targetSum - 当前节点值

不断递减。

若：

count == 0

且到达叶子节点：

则找到目标路径。

if (!cur->left && !cur->right && count == 0) {
    return true;
}

if (!cur->left && !cur->right) {
    return false;
}

3、确定单层递归逻辑

由于终止条件是叶子节点：

因此不要让空节点进入递归。

若递归函数有返回值：

找到答案后应立刻返回。

T98 验证二叉搜索树

摘录《代码随想录》笔记：

陷阱1

不能只比较：

root->left < root < root->right

错误代码：

if (root->val > root->left->val &&
    root->val < root->right->val) {

    return true;
}

错误原因：

BST 要求：

左子树所有节点 < root
右子树所有节点 > root

而不是仅比较左右孩子。

反例：

[10,5,15,null,null,6,20]

虽然：

5 < 10 < 15

但：

6 < 10

出现在右子树中。

因此不是 BST。

陷阱2

最小值可能是：

INT_MIN

因此不能用 int 最小值做初始比较。

应使用：

long long

中序遍历解法

BST 中序遍历一定严格递增。

class Solution {
private:

    vector<int> vec;

    void traversal(TreeNode* root) {

        if (root == nullptr) return;

        traversal(root->left);

        vec.push_back(root->val);

        traversal(root->right);
    }

public:

    bool isValidBST(TreeNode* root) {

        vec.clear();

        traversal(root);

        for (int i = 1; i < vec.size(); i++) {

            // BST 不允许重复元素
            if (vec[i] <= vec[i - 1]) {
                return false;
            }
        }

        return true;
    }
};

Share on

X Facebook LinkedIn Bluesky