【算法与数据结构】669、LeetCode修剪二叉搜索树

所有的LeetCode题解索引，可以看这篇文章——【算法和数据结构】LeetCode题解。

一、题目

二、解法

  思路分析：450、LeetCode删除二叉搜索树中的节点两道题的思路几乎是一样的，只不过终止条件和单层递归逻辑的顺序需要调换，因为本题需要删除的可能不止一个节点，需要先递归到最深处（只要节点非空），然后进行判断，否则在根节点为[low, high]区间外时它把根节点一删除就没有后续操作了，但此时树里面可能还有区间外的节点，造成漏删。删除类型一共有5种，450题已经分析过了。
  程序如下：

class Solution {
public:
    TreeNode* trimBST(TreeNode* root, int low, int high) {
        if (root == NULL) return root;  // 没找到节点
        root->left = trimBST(root->left, low, high);
        root->right = trimBST(root->right, low, high);

        if (root->val < low || root->val > high) {         // 找到节点
            if (root->right == NULL && root->left == NULL) {    // 左右孩子均为空，返回空节点
                return NULL;
            }
            else if (root->left == NULL) {  // 左孩子为空，右孩子不为空，返回右孩子
                auto retNode = root->right;
                return retNode;
            }
            else if (root->right == NULL) { // 右孩子为空，左孩子不为空，返回左孩子
                auto retNode = root->left;
                return retNode;
            }
            else {  // 左右孩子均不为空，左孩子补位到右孩子最底层最左边的节点上  
                TreeNode* cur = root->right;
                while (cur->left != NULL) {
                    cur = cur->left;
                }
                cur->left = root->left;
                auto retNode = root->right;
                return retNode;
            }
        }
        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

复杂度分析：

• 时间复杂度： $O(n)$，需要遍历每一个元素。
• 空间复杂度：$O(n)$，最坏情况下，递归深度为n。

三、完整代码

# include 
# include 
# include 
# include 
using namespace std;

// 树节点定义
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    TreeNode* trimBST(TreeNode* root, int low, int high) {
        if (root == NULL) return root;  // 没找到节点
        root->left = trimBST(root->left, low, high);
        root->right = trimBST(root->right, low, high);

        if (root->val < low || root->val > high) {         // 找到节点
            if (root->right == NULL && root->left == NULL) {    // 左右孩子均为空，返回空节点
                return NULL;
            }
            else if (root->left == NULL) {  // 左孩子为空，右孩子不为空，返回右孩子
                auto retNode = root->right;
                return retNode;
            }
            else if (root->right == NULL) { // 右孩子为空，左孩子不为空，返回左孩子
                auto retNode = root->left;
                return retNode;
            }
            else {  // 左右孩子均不为空，左孩子补位到右孩子最底层最左边的节点上  
                TreeNode* cur = root->right;
                while (cur->left != NULL) {
                    cur = cur->left;
                }
                cur->left = root->left;
                auto retNode = root->right;
                return retNode;
            }
        }
        return root;
    }
};

// 前序遍历迭代法创建二叉树，每次迭代将容器首元素弹出（弹出代码还可以再优化）
void Tree_Generator(vector<string>& t, TreeNode*& node) {
    if (!t.size() || t[0] == "NULL") return;    // 退出条件
    else {
        node = new TreeNode(stoi(t[0].c_str()));    // 中
        if (t.size()) {
            t.assign(t.begin() + 1, t.end());
            Tree_Generator(t, node->left);              // 左
        }
        if (t.size()) {
            t.assign(t.begin() + 1, t.end());
            Tree_Generator(t, node->right);             // 右
        }
    }
}

template<typename T>
void my_print(T& v, const string msg)
{
    cout << msg << endl;
    for (class T::iterator it = v.begin(); it != v.end(); it++) {
        cout << *it << ' ';
    }
    cout << endl;
}

template<class T1, class T2>
void my_print2(T1& v, const string str) {
    cout << str << endl;
    for (class T1::iterator vit = v.begin(); vit < v.end(); ++vit) {
        for (class T2::iterator it = (*vit).begin(); it < (*vit).end(); ++it) {
            cout << *it << ' ';
        }
        cout << endl;
    }
}

// 层序遍历
vector<vector<int>> levelOrder(TreeNode* root) {
    queue<TreeNode*> que;
    if (root != NULL) que.push(root);
    vector<vector<int>> result;
    while (!que.empty()) {
        int size = que.size();  // size必须固定, que.size()是不断变化的
        vector<int> vec;
        for (int i = 0; i < size; ++i) {
            TreeNode* node = que.front();
            que.pop();
            vec.push_back(node->val);
            if (node->left) que.push(node->left);
            if (node->right) que.push(node->right);
        }
        result.push_back(vec);
    }
    return result;
}

int main()
{
    // 构建二叉树
    //vector t = { "3", "0", "NULL", "2", "1", "NULL", "NULL", "NULL", "4", "NULL", "NULL" };   // 前序遍历
    //vector t = { "1", "NULL", "2", "NULL", "NULL"};   // 前序遍历
    vector<string> t = { "2", "1", "NULL", "NULL", "3", "NULL", "NULL" };   // 前序遍历
    my_print(t, "目标树");
    TreeNode* root = new TreeNode();
    Tree_Generator(t, root);
    vector<vector<int>> tree = levelOrder(root);
    my_print2<vector<vector<int>>, vector<int>>(tree, "目标树:");

    // 删除目标值
    int low = 3;
    int high = 4;
    Solution s;
    TreeNode* result = s.trimBST(root, low, high);
    vector<vector<int>> tree1 = levelOrder(result);
    my_print2<vector<vector<int>>, vector<int>>(tree1, "结果树:");

    system("pause");
    return 0;
}
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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129

end