字数统计: 3.4k字   |   阅读时长: 16分

二叉树 (5)

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

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

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

思路：根据二叉搜索树的特点，如果cur节点的值在[p，q]范围内就认为找到了公共祖先。

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;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root->val > p->val && root->val > q->val)
        return lowestCommonAncestor(root->left, p, q);
        else if(root->val < p->val && root->val < q->val)
        return lowestCommonAncestor(root->right, p, q);
        else 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
//迭代法,先序遍历
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

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

701. 二叉搜索树中的插入操作 - 力扣（LeetCode） (leetcode-cn.com)

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

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

思路：因为题目没有要求插入方式，实际上只需要遍历找到空节点插入即可。

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
/**
 * Definition for a binary tree node.
 * 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* 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;
    }
};
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
//迭代法，通过cur确定插入元素的位置,pre记录插入位置的父节点,新建一个node作为插入的对象
/**
 * Definition for a binary tree node.
 * 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* insertIntoBST(TreeNode* root, int val) {
        if(root == NULL)
        {
            TreeNode* node = new TreeNode(val);
            return node;
        }
        TreeNode* pre = NULL; //迭代法，定义一个pre作为cur的上一个节点,通过pre插入node节点
        TreeNode* cur = root;
        while(cur != NULL)
        {
            pre = cur;
            if(cur->val > val)  cur = cur->left;
            else    cur = cur->right;
        }
        TreeNode* node = new TreeNode(val);
        if(pre->val > val) pre->left = node;
        else pre->right = node;
        return root;
    }
};

450. 删除二叉搜索树中的节点 - 力扣（LeetCode） (leetcode-cn.com)

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

一般来说，删除节点可分为两个步骤：

首先找到需要删除的节点；
如果找到了，删除它。

思路：有以下五种情况：

  • 第一种情况：没找到删除的节点，遍历到空节点直接返回了
  • 找到删除的节点
    • 第二种情况：左右孩子都为空（叶子节点），直接删除节点， 返回NULL为根节点
    • 第三种情况：删除节点的左孩子为空，右孩子不为空，删除节点，右孩子补位，返回右孩子为根节点
    • 第四种情况：删除节点的右孩子为空，左孩子不为空，删除节点，左孩子补位，返回左孩子为根节点
    • 第五种情况：左右孩子节点都不为空，则将删除节点的左子树头结点（左孩子）放到删除节点的右子树的最左面节点的左孩子上，返回删除节点右孩子为新的根节点。见下面的动图。

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
//递归法
/**
 * Definition for a binary tree node.
 * 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* deleteNode(TreeNode* root, int key) {
        if(root == NULL) return root;//第一种情况，没有找到key
        if(root->val == key)
        {
            //第二种情况:找到key，且为叶子节点
            if(root->left == nullptr && root->right == nullptr)
            {
                delete(root);
                return nullptr;
            }
            //第三种情况:左子树为空，右子树不为空
            else if(root->left == nullptr)
            {
                TreeNode* node = root->right;
                delete root;
                return node;
            }
            //第四种情况:左子树为空，右子树不为空
            else if(root->right == nullptr)
            {
                TreeNode* node = root->left;
                delete root;
                return node;
            }
            //第五种情况：左右子树都不为空
            else
            {
                TreeNode *cur = root->right;//找右子树最左边的节点
                while(cur->left != nullptr)
                {
                    cur = cur->left;
                }
                cur->left = root->left; //将root的左子树作为root右子树最左边节点的左子树
                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;
    }
};

递归法的思路，就考虑特殊情况怎么处理，比如要找的值在根节点，或者直接就是根节点的左右孩子的情况，考虑一层的逻辑，通过递归就可以实现整个树的逻辑。

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
/**
 * Definition for a binary tree node.
 * 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 {
private:
    TreeNode* deleteOneNode(TreeNode* root) //删除一个节点的逻辑
    {
        if(root == nullptr) return root;
        if(root->left == NULL && root->right ==NULL) return NULL;//第二种情况
        if(root->right == NULL) return root->left;//第三种情况
        if(root->left == NULL) return root->right;//第四种情况
        TreeNode* cur = root->right; //对应第五种情况
        while(cur->left != NULL)
        {
            cur = cur->left;
        }
        cur->left = root->left;
        return root->right;
    }
public:
    TreeNode* deleteNode(TreeNode* root, int key) { 
        if(root == nullptr) return root;
        TreeNode* cur = root;
        TreeNode* pre = nullptr;//pre为cur的前一个节点
        while(cur != nullptr)
        {
            if(cur->val == key) break;
            pre = cur;
            if(cur->val > key) cur = cur->left;
            else cur = cur->right;
        }
        if(pre == nullptr) return deleteOneNode(cur);
        if(pre->left != nullptr && pre->left->val == key)
        pre->left = deleteOneNode(cur);
        if(pre->right != nullptr && pre->right->val == key)
        pre->right = deleteOneNode(cur);
        return root;
    }
};

模拟递归法中的逻辑来删除节点，定义的一个删除节点的函数，需要一个pre记录cur的父节点，方便做删除操作。

669. 修剪二叉搜索树 - 力扣（LeetCode） (leetcode-cn.com)

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

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

思路：本质上就是删除结点，如果某个结点小于low，就递归判断它的右子树是否位于区间内；如果结点大于high，就判断它的左子树是否位于区间内。

迭代法：因为二叉搜索树的有序性，不需要使用栈模拟递归的过程。

在剪枝的时候，可以分为三步：

  • 将root移动到[L, R] 范围内，注意是左闭右闭区间
  • 剪枝左子树
  • 剪枝右子树
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
/**
 * Definition for a binary tree node.
 * 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 == nullptr) return root;
        while(root != nullptr && (root->val < low || root->val > high))
        {
            if(root->val < low) root = root->right;
            else root = root->left;
        }
        TreeNode* cur = root;
        //处理左孩子小于low的情况
        while(cur != nullptr) //一直遍历完整棵树小于low的结点
        {
            while(cur->left != nullptr && cur->left->val < low) //注意用while不能用if
            cur->left = cur->left->right; //将不小于low的左孩子的右子树接在原来左孩子的位置上
            cur = cur->left;//新接入的cur->left作为cur
        }
        cur = root; //将cur移到根节点处
        while(cur != nullptr)
        {
            while(cur->right != nullptr && cur->right->val > high)
            cur->right = cur->right->left;
            cur = cur->right;
        }
        return root;
    }
};

108. 将有序数组转换为二叉搜索树 - 力扣（LeetCode） (leetcode-cn.com)

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

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

思路：类似于二分查找，只要把数组中间的元素作为根节点，得到的二叉树一定是高度平衡的。不断递归分割，然后分别处理左子树和右子树，要注意循环不变量的重要性。

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
//递归法
/**
 * Definition for a binary tree node.
 * 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 {
private:
    TreeNode* traversal(vector<int> &nums, int left, int right)
    {
        if(left > right) return nullptr;
        int mid = left + (right - left) / 2; //注意不要用(left + right) / 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;
    }
};

迭代法可以通过三个队列来模拟，一个队列放遍历的节点，一个队列放左区间下标，一个队列放右区间下标。

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
//迭代法
/**
 * Definition for a binary tree node.
 * 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* sortedArrayToBST(vector<int>& nums) {
        if(nums.size() == 0) return nullptr;
        TreeNode* root = new TreeNode(0);
        queue <TreeNode*> nodeQue;//放遍历的结点
        queue <int> leftQue;//记录下标
        queue <int> rightQue;//记录下标
        nodeQue.push(root);
        leftQue.push(0);
        rightQue.push(nums.size() - 1);//左闭右闭的区间
        while(!nodeQue.empty())
        {
            TreeNode* curNode = nodeQue.front();
            nodeQue.pop();
            int left = leftQue.front();
            leftQue.pop();
            int right = rightQue.front();
            rightQue.pop();
            int mid = left + (right - left) / 2;
            curNode->val = nums[mid];
            if(left <= mid - 1)
            {
                curNode->left = new TreeNode(0);
                nodeQue.push(curNode->left);
                leftQue.push(left);
                rightQue.push(mid - 1);
            }
            if(right >= mid + 1)
            {
                curNode->right = new TreeNode(0);
                nodeQue.push(curNode->right);
                leftQue.push(mid + 1);
                rightQue.push(right);
            }
        }
        return root;

    }
};

538. 把二叉搜索树转换为累加树 - 力扣（LeetCode） (leetcode-cn.com)

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

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

节点的左子树仅包含键 小于 节点键的节点。
节点的右子树仅包含键 大于 节点键的节点。
左右子树也必须是二叉搜索树。

实际上就是对树进行中序遍历，得到递增的数组，比如[2, 5, 13]，然后求从后到前的累加数组，也就是[20, 18, 13]；实际上应该是逆中序遍历，每次遍历时将当前的数加上上一个数作为最后结果即可。

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
//递归法
/**
 * Definition for a binary tree node.
 * 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 {
private:
    int pre;
    void traversal(TreeNode* cur)
    {
        if(cur == NULL) return;
        traversal(cur->right);
        cur->val = pre + cur->val;
        pre = cur->val;
        traversal(cur->left);
    }
public:
    TreeNode* convertBST(TreeNode* root) {
        pre = 0;
        traversal(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
/**
 * Definition for a binary tree node.
 * 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* convertBST(TreeNode* root) {
        int pre = 0;
        stack <TreeNode*> st;
        TreeNode* cur = root;
        while(!st.empty() || cur != nullptr)
        {
            if(cur != nullptr)
            {
                st.push(cur);
                cur = cur->right;
            }
            else
            {
                cur = st.top();
                st.pop();
                cur->val = pre + cur->val;
                pre = cur->val;
                cur = cur->left;
            }
        }
        return root;
    }
};

扫一扫，分享到微信

微信分享二维码
本站总访问量次 |

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

这一定是一个<br><br>很长很长的一生啊