2019獨(dú)角獸企業(yè)重金招聘Python工程師標(biāo)準(zhǔn)>>>

題目描述

給定一顆二叉搜索樹，請(qǐng)找出其中的第k大的結(jié)點(diǎn)。例如， 5 / \ 3 7 /\ /\ 2 4 6 8 中，按結(jié)點(diǎn)數(shù)值大小順序第三個(gè)結(jié)點(diǎn)的值為4。

【解決】

① 使用一個(gè)變量記錄遍歷的個(gè)數(shù)

class TreeNode {
? ? int val = 0;
? ? TreeNode left = null;
? ? TreeNode right = null;
? ? public TreeNode(int val) {
? ? ? ? this.val = val;
? ? }
}
public class Solution {
? ? int count = 0;
? ? TreeNode KthNode(TreeNode pRoot, int k) {
? ? ? ? if (pRoot == null || k <= 0){
? ? ? ? ? ? return null;
? ? ? ? }
? ? ? ? TreeNode res = null;
? ? ? ? if (pRoot.left != null){
? ? ? ? ? ? res = KthNode(pRoot.left,k);
? ? ? ? }
? ? ? ? count ++;
? ? ? ? if (res == null){
? ? ? ? ? ? if (count == k){
? ? ? ? ? ? ? ? res = pRoot;
? ? ? ? ? ? ? ? return res;
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? if (res == null && pRoot.right != null){
? ? ? ? ? ? res = KthNode(pRoot.right,k);
? ? ? ? }
? ? ? ? return res;
? ? }
}

② 使用一個(gè)變量保存中序遍歷的結(jié)果

import java.util.ArrayList;
import java.util.List;

class TreeNode {
? ? int val = 0;
? ? TreeNode left = null;
? ? TreeNode right = null;
? ? public TreeNode(int val) {
? ? ? ? this.val = val;
? ? }
}
public class Solution {
? ? List<TreeNode> list = new ArrayList<>();
? ? TreeNode KthNode(TreeNode pRoot, int k) {
? ? ? ? if (k == 0) return null;
? ? ? ? inorder(pRoot);
? ? ? ? if (k > list.size()) return null;
? ? ? ? return list.get(k - 1);
? ? }
? ? public void inorder(TreeNode root){
? ? ? ? if (root == null) return;
? ? ? ? inorder(root.left);
? ? ? ? list.add(root);
? ? ? ? inorder(root.right);
? ? }
}

轉(zhuǎn)載于:https://my.oschina.net/liyurong/blog/1678807

總結(jié)

以上是生活随笔為你收集整理的二叉搜索树的第k个结点的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。