Shulou(Shulou.com)06/01 Report--

This article mainly introduces how leetCode finds the kth node of the binary search tree. The introduction in this article is very detailed and has certain reference value. Interested friends must read it!

1. The kth node of the binary search tree 1. Brief description of the problem

Given a binary search tree, find the kth largest node.

2, Example Description Example 1:

Input: root = [3,1,4,null,2], k = 1

3

/ \

1 4

\

2

output: 4

Example 2:

Input: root = [5,3,6,2,4,null,null,1], k = 3

5

/ \

3 6

/ \

2 4

/

1

output: 4

Limitations:

1 ≤ k ≤ number of binary search tree elements

3, the solution to the problem

Binary search tree is the element of the order traversal of incremental, according to the order of traversal of the data can be solved.

4, the solution program

import java.util.ArrayList;

import java.util.Comparator;

import java.util.List;

public class KthLargestTest3 {

public static void main(String[] args) {

TreeNode t1=new TreeNode(3);

TreeNode t2=new TreeNode(1);

TreeNode t3=new TreeNode(4);

TreeNode t4=new TreeNode(2);

t1.left=t2;

t1.right=t3;

t2.right=t4;

int k=1;

int kthLargest = kthLargest(t1, k);

System.out.println("kthLargest = " + kthLargest);

}

public static int kthLargest(TreeNode root, int k) {

if (root == null) {

return 0;

}

List list = new ArrayList();

dfs(root, list);

list.sort(Comparator.reverseOrder());

return list.get(k - 1);

}

private static void dfs(TreeNode root, List list) {

if (root == null) {

return;

}

if (root.left != null) {

dfs(root.left, list);

}

list.add(root.val);

if (root.right != null) {

dfs(root.right, list);

}

}

}

The above is "leetCode how to find the kth node of binary search tree" all the content of this article, thank you for reading! Hope to share the content to help everyone, more relevant knowledge, welcome to pay attention to the industry information channel!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.