地址 https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-di-kda-jie-dian-lcof/
给定一棵二叉搜索树,请找出其中第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大的节点
3 / 1 4 2 5 / 3 6 / 2 4 / 1
class Solution { public: int ans = 0; int kk; void dfs(TreeNode* root) { if(root==NULL) return; dfs(root->right); kk -= 1; if(kk==0){ ans = root->val;} dfs(root->left); return; } int kthLargest(TreeNode* root, int k) { kk = k; dfs(root); return ans; } };