LeetCode 二叉搜索树的第K大节点/二叉搜索树转化为累加树

这是我参与更文挑战的第 26 天，活动详情查看： 更文挑战

二叉搜索树的第 K 大节点（剑指 Offer 54）

题目描述

给定一棵二叉搜索树，请找出其中第k大的节点。

示例 1：

输入: root = [3,1,4,null,2], k = 1
   3
  / \
 1   4
  \
   2
输出: 4
复制代码

示例 2：

输入: root = [5,3,6,2,4,null,null,1], k = 3
       5
      / \
     3   6
    / \
   2   4
  /
 1
输出: 4
复制代码

限制

1 ≤ k ≤ 二叉搜索树元素个数

思路分析

二叉搜索树的第 K 大节点，这个问题有点类似有求一个数组中的第 K 大节点，只不过这里是二叉树，二叉树搜索树的中序就是从小到大，但是我们可以不需要把所有值的排序完整，只要找到第 K 大就行了。

代码展示

解法一：

int res,k;
    public int kthLargest(TreeNode root, int k) {
        // List<Integer> result = new ArrayList<>();
        // inorder(root,result);
        // int index = result.size() - k;
        // return result.get(index);
        
        //中序遍历  从小到大：左-根-右    从大到小：右-根-左 
        this.k = k;
        inorder(root);
        return res;
    }

    private void inorder(TreeNode node){
        if(node == null){
            return;
        }
        inorder(node.right);
        if(k == 0){
            return;
        }
        if(--k == 0){
            res = node.val;
        }
        inorder(node.left);
    }

    // private void inorder(TreeNode node,List<Integer> result){
    //     Stack<TreeNode> stack = new Stack<>();
    //     while(!stack.isEmpty() || node != null){
    //         while(node != null){
    //             stack.push(node);
    //             node = node.left;
    //         }
    //         node = stack.pop();
    //         result.add(node.val);
    //         node = node.right;
    //     }
    // }
复制代码

二叉搜索树转化为累加树（538）

题目描述

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

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

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

示例 1：

输入：[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
输出：[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]
复制代码

示例 2：

输入：root = [0,null,1]
输出：[1,null,1]
复制代码

示例 3：

输入：root = [1,0,2]
输出：[3,3,2]
复制代码

示例 4：

输入：root = [3,2,4,1]
输出：[7,9,4,10]
复制代码

• 提示：
  • 树中的节点数介于 0 和 104 之间。
  • 每个节点的值介于 -104 和 104 之间。
  • 树中的所有值 互不相同 。
  • 给定的树为二叉搜索树。

思路分析

二叉搜索树转化为累加树，因为二叉搜索树有个特征：节点的左子树仅包含键 小于 节点键的节点。节点的右子树仅包含键 大于 节点键的节点。左右子树也必须是二叉搜索树。我们知道二叉搜索树的中序遍历是由大到小，但是累加树的特征是使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。

我们可以将中序遍历改一下，先遍历右边的节点，在遍历左边的节点，就是从大到小的，所以遍历过的节点都是大于该节点值，我们只需要给它累加起来就像，递归遍历。

代码展示

解法一：

    int sum = 0;
    public TreeNode convertBST(TreeNode root) {
        if(root == null){
            return null;
        }
        convertBST(root.right);
        sum += root.val;
        root.val = sum;
        convertBST(root.left);
        return root;
    }
复制代码

总结

二叉搜索树的中序遍历后的结果是从小到大的遍历结果。