东哥带你刷二叉搜索树（特性篇） :: labuladong的算法小抄

[utterances-bot]

文章链接点这里：东哥带你刷二叉搜索树（特性篇）

评论礼仪 见这里，违者直接拉黑。

[JingweiZuo]

如何让每一个节点知道自己的排名？每个节点需要记录，以自己为根的这棵二叉树有多少个节点。有了 size 字段，外加 BST 节点左小右大的性质，对于每个节点 node 就可以通过 node.left 推导出 node 的排名

这一段表述不太理解，知道以自己为根的这棵二叉树有多少个节点后 对计算此节点的排名有什么帮助？

[labuladong]

BST 左小右大，所以节点 x 的左子树的节点个数可以推导出 x 的排名

[YiyanChen]

东哥这里还是有点不懂，拿文里230题给的例子，节点4的左子树节点个数是0，可是4应该排在整棵树的第4位，size是要包含整个左边吗？

[wild-chigga]

YiyanChen的疑问+1

[wangbaonan]

YiyanChen的疑问+2

[labuladong]

直接把伪码列出来，应该就容易理解了：

class TreeNode {
    TreeNode left, right;
    int val;
    // 记录当前节点为根的二叉树共有多少节点
    int size;
}

// 伪码逻辑
// 定义：返回 target 节点在以 root 为根的二叉树上的排名
int rank(TreeNode root, TreeNode target) {
    if (target.val == root.val) {
        // 左子树节点个数 + 1 就是排名
        return root.left.size + 1;
    } else if (target.val < root.val) {
        // target 比较小，去左子树算排名
        return rank(root.left, target);
    } else if (target.val > root.val) {
        // target 比较大，整棵左子树加上当前 root 节点都比它小，
        // 同时右子树里可能还有比它小的，让递归去算
        return 1 + root.left.size + rank(root.right, target);
    }
}

[zxc948406613]

那算第k小的节点的时候，每次对比当前节点的时候，都得去计算出左子树节点的个数和总子树个数么？

[labuladong]

@zxc948406613 如果能够把节点的个数存到 TreeNode 里面，直接就可以拿到

[algorithmDeng]

@labuladong 那如果是叶子节点没有左子树应该怎么推导

[wercyle]

分解问题的思路：
后序遍历获得子树和，形参传递大于子树的父结点值之和

 TreeNode* convertBST(TreeNode* root) {
        SumTree(root,0);
        return root;
    }
    

    int SumTree(TreeNode* root,int right){
        if(!root) return 0;

        int RightSum=SumTree(root->right,right);
        int LeftSum=SumTree(root->left,right+root->val+RightSum);
        
        int original_root_val=root->val;
        root->val+=RightSum+right;
        

        return LeftSum+RightSum+original_root_val;
    }

[sonymoon]

太绕了。。

[wojoin]

东哥yyds, 看了核心框架篇后刷了些数组和链表题，就立马来刷二叉树了，逐渐有点感觉了

[LeeHaruYa]

滴滴滴打卡

[shiyang07ca]

BST 转化累加树中的递归函数，为什么要把 sum 作为外部累加变量，而不能是递归函数的一个参数？

[wild-chigga]

inorder(root.left, pre_sum)中pre_sum更新为pre_sum_new， 但inorder(root.right, pre_sum)传入的还是老的pre_sum

[yonggui-yan]

打卡打卡

比上一篇简单多了！

[shallowshadowshade]

打卡第一题，中序遍历存储后返回索引为k-1的即可

class Solution {
private:
    vector<int> res;
public:
    int kthSmallest(TreeNode* root, int k) {
        traverse(root);
        return res[k - 1];
    }

    void traverse(TreeNode* root)
    {
        if (root == nullptr) return;
        traverse(root->left);
        res.push_back(root->val);//BST中序遍历，在这里保存一个数值
        traverse(root->right);
        return;
    }
};

[jxs1211]

the key is the inorder slice which is ascend order, here is the solution of go version

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func kthSmallest(root *TreeNode, k int) int {
    res := dfs(root)
    fmt.Println(res)
    for i, v := range res {
        if i == k - 1 {return v}
    }
    return 0
}

func dfs(root *TreeNode) []int {
    res := []int{}
    if root == nil {return res}
    res = append(res, dfs(root.Left)...)
    res = append(res, root.Val)
    res = append(res, dfs(root.Right)...)
    return res
}

[jxs1211]

230. Kth Smallest Element in a BST

[jxs1211]

538. Convert BST to Greater Tree and 1038. Binary Search Tree to Greater Sum Tree
     The key is the build a inorder slice which gather the values of the tree node in descend order.
     Here is the solution of go version.

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func convertBST(root *TreeNode) *TreeNode {
    sum := 0
    traverse(root, &sum)
    return root
}

func traverse(root *TreeNode, sum *int) {
    if root == nil {return}
    traverse(root.Right, sum)
    *sum += root.Val
    root.Val = *sum
    traverse(root.Left, sum)
}

[yangzerenmiku]

2022.11.2 打卡

[kafeijk]

这个地方：如果 k > m，那说明排名第 k 的元素在右子树，所以可以去右子树搜索第 k - m - 1 个元素。
不知道为什么要多减个1，k - m - 1作为k在右子树上面的排名，是不能等于0的吧

[kafeijk]

以上文第230题为例，假设k为6，节点5(m=5)要找的是右子树的第1个节点即k-m，而不是第0(k-m-1)个吧，而且root.left.size + 1为排名大小的话最小也是1不是0

[daiqian0930]

理解为找下标为k的节点，k从0开始递增。同样地，假设k为6，节点5(m=5)要找的是右子树的下标为k-m-1=0的节点。

[xxc516]

请问一下“对于一个节点来说，确实右子树都是比它大的元素，但问题是它的父节点也可能是比它大的元素呀”这里是什么意思啊

[xxc516]

懂了懂了打扰了

[yusun97]

第230题 类似于增加size字段的方法
统计左子树的总节点数量left + 1 并与K进行比较

• 如果left + 1< k 说明第k小的数在左子树里 递归kthSmallest(root.left, k)
• 如果left + 1> k 说明第k小的数在右子树里 递归kthSmallest(root.right, k - (left + 1))
  （已知左子树有left个节点 当前root是一个节点 要在右子树里查找 应当是找第k - (left + 1)小的数）
• 如果left + 1== k 说明第k小的数就是当前root

class Solution {
    public int kthSmallest(TreeNode root, int k) {
        int left = numberNodes(root.left);

        if(k < left + 1) return kthSmallest(root.left, k); 
        else if(k > left + 1) return kthSmallest(root.right, k - (left + 1));
        else return root.val;
    }

    public int numberNodes(TreeNode root){
        if(root == null) return 0;
        return numberNodes(root.left) + numberNodes(root.right) + 1;
    }
}

[AndyWu0107]

230的解法可以做一点优化：在traverse函数里，

    if (k == rank) {
        // 找到第 k 小的元素
        res = root.val;
        return;
    }

可以加个分支

        else if (rank> k)
        {
            return;
        }

这样可以避免在找到想要的元素之后及时返回，而不是又继续往右子树遍历。

[F0restN]

01092023 Check

[CarlLy7]

打卡

[chitongyu]

当我自己去创建一个累加树的时候，规律就被发现了，很神奇。我开始也是打算保存父节点且考虑左右子节点分别处理，后面自己在图上画画累加树就看见规律了，哈哈，发一下癫！

[forexgg]

为啥两个题目，一模一样，奇怪。