通知 网站从因情语写改为晴雨,这个网站的模板也从calmlog_ex改为 whimurmur

leetcode 剑指 Offer 54. 二叉搜索树的第k大节点

72人浏览 / 0人评论 / | 作者:whisper  | 分类: 剑指offer2  | 标签: 剑指offer2  | 

作者:whisper

链接:https://www.proprogrammar.com/article/877

声明:请尊重原作者的劳动,如需转载请注明出处


剑指 Offer 54. 二叉搜索树的第k大节点

给定一棵二叉搜索树,请找出其中第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 ≤ 二叉搜索树元素个数


难度:简单;标签:树;编程语言:C++


我的解法

/**
 * 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:
    int kthLargest(TreeNode* root, int k) {
        return kthLargest(root, &k);
    }
    
    int kthLargest(TreeNode* node, int* k){
        return node ? (kthLargest(node->right, k) ? *k : ((*k)-- == 1 ? *k = node->val : kthLargest(node->left, k))) : 0;
    }
};

自己写的,看了半天看不懂,大概就是找第K大,那先右后当前后左,先一直右,直到null(此时*k不变且大于0),那么当前(*k)--,为0时return,否则再向左,结合二叉树想像这个过程比较容易理解,这里这样写就是代码的trick(技巧)

二叉搜索树是有序的,如果找有序的第k个,就是先左后当前后右,这里是第K大,所以是先右后当前后左


其它解法

class Solution {
    public:
        int rst;
        int cout;
        int kthLargest(TreeNode* root, int k) {
            cout = k;
            re_inorder(root);
            return rst;
        }
        void re_inorder(TreeNode* cur){
            if(cur == NULL || cout==0){
                return;
            }
            re_inorder(cur->right);
            if(--cout==0){
                rst = cur->val;
                return;
            }
            re_inorder(cur->left);
        }
    };

上面就比较好理解了,反中序遍历,从大到小,返回遍历到的第K个数


亲爱的读者:有时间可以点赞评论一下

点赞(0) 打赏

全部评论

还没有评论!
广告位-帮帮忙点下广告