剑指offer-二叉搜索树的第k大节点

二叉搜索树的第k大节点

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

示例

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

思路

方案一：利用中序遍历，把所有的值放到一个数组里面，遍历结束后，返回arr[arr.length-k]，即是所求。

方案二：利用逆中序遍历（右-根-左）,依次k–，当k等于0，说明已经达到第k大的节点了，这个节点即是所求

代码

// 方案1代码
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} k
 * @return {number}
 */
var kthLargest = function(root, k) {
    if (root == null) {
        return null;
    }
    const res = inOrderTraverse(root);
    return res[res.length - k];
};

function inOrderTraverse(root, arr = []) {
    root.left && inOrderTraverse(root.left, arr);
    arr.push(root.val);
    root.right && inOrderTraverse(root.right, arr);
    return arr;
}

方案二代码：
function kthLargest(root, k) {
    if (root === null || k === 0) {
        return null;
    }
    let max = null;
    function kthLargestCore(root) {
        if (!root) return;
        kthLargestCore(root.right);
        if (--k === 0) {
            return max = root.val;
        }
        kthLargestCore(root.left);
    }
    kthLargestCore(root);
    return max;
}

复杂度分析:

方案一：

时间复杂度: O(N)
空间复杂度：O(N)

方案二：

时间复杂度: O(N)
空间复杂度：O(1)

FEATURED TAGS

前端开发 H5 JavaScript 设计模式 browser jQuery 源码分析生活 leetcode Array Stack Queue Linked List 剑指offer Binary Search Tree Binary Tree Breadth-First Search Depth-First Search String Set Binary Search Sliding Window Backtracking Dynamic Programming Two Pointers Union Find Sort Bit Operation Recursion Map Graph Search Hash LinkedList 复盘 QuickSort Trie Design MinHeap Traverse Min Heap Node.js BackEnd SQL MySQL Design Patterns Network 计算机网络 Python SVG

二叉搜索树的第k大节点

思路

代码

CATALOG

FEATURED TAGS

FRIENDS