剑指offer（62）二叉搜索树的第K个节点（二叉搜索树的第k个结点）

25-03-12 9

针对剑指offer和62二叉搜索树的第K个节点这两个问题，本篇文章进行了详细的解答，同时本文还将给你拓展C#刷剑指Offer|二叉搜索树的后序遍历序列、JZ62二叉搜索树的第k个结点、LeetCode

针对剑指offer和62二叉搜索树的第K个节点这两个问题，本篇文章进行了详细的解答，同时本文还将给你拓展C#刷剑指Offer | 二叉搜索树的后序遍历序列、JZ62 二叉搜索树的第k个结点、LeetCode Java刷题笔记—剑指 Offer 54. 二叉搜索树的第k大节点、《剑指offer》链表中倒数第k个节点等相关知识，希望可以帮助到你。

本文目录一览：

剑指offer（62）二叉搜索树的第K个节点（二叉搜索树的第k个结点）
C#刷剑指Offer | 二叉搜索树的后序遍历序列
JZ62 二叉搜索树的第k个结点
LeetCode Java刷题笔记—剑指 Offer 54. 二叉搜索树的第k大节点
《剑指offer》链表中倒数第k个节点

剑指offer（62）二叉搜索树的第K个节点（二叉搜索树的第k个结点）

题目描述

给定一棵二叉搜索树，请找出其中的第k小的结点。例如，（5，3，7，2，4，6，8）中，按结点数值大小顺序第三小结点的值为4。

题目分析

首先，我们可以先画图。画完图后我们要想办法从中找出第K小的节点。

因为这是二叉搜索树，我们可以轻易发现它的中序遍历序列就是从小到大排列，也就是我们可以直接中序遍历，同时计数，就可以得到我们想要的节点了。

不过需要注意的是我们的计数变量k应该在函数外面，不然递归进去后回来时是无法获得已经改变了的k值的。

代码

function KthNode(pRoot, k) {
  if (pRoot === null || k === 0) {
    return null;
  }
  // 为了能追踪k，应该把KthNodeCore函数定义在这里面，k应该在KthNodeCore函数外面
  function KthNodeCore(pRoot) {
    let target = null;
    if (pRoot.left !== null) {
      target = KthNodeCore(pRoot.left, k);
    }
    if (target === null) {
      if (k === 1) {
        target = pRoot;
      }
      k--;
    }
    if (target === null && pRoot.right !== null) {
      target = KthNodeCore(pRoot.right, k);
    }
    return target;
  }
  return KthNodeCore(pRoot);
}

C#刷剑指Offer | 二叉搜索树的后序遍历序列

【C#刷题】| 作者 / Edison Zhou

这是 EdisonTalk 的第 289 篇原创内容

我们来用之前学到的数据结构知识来刷《剑指Offer》的一些核心题目（精选了其中30+道题目），希望对你有帮助！本文题目为：二叉搜索树的后序遍历序列。

1题目介绍

题目：输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回true，否则返回false。假设输入的数组的任意两个数字都互不相同。

例如在下面的一颗二叉搜索树中，输入数组{5,7,6,9,11,10,8}，则返回true，因为这个整数序列是下图二叉搜索树的后序遍历结果。如果输入的数组是{7,4,6,5}，由于没有哪棵二叉搜索树的后序遍历的结果是这个序列，因此返回false。

2解题思路与实现

思路：

在后序遍历得到的序列中，最后一个数字是树的根结点的值。数组中前面的数字可以分为两部分：第一部分是左子树结点的值，它们都比根结点的值小；第二部分是右子树结点的值，它们都比根结点的值大。

因此，我们可以总结出算法步骤：

Step1.通过取出序列最后一个元素得到二叉搜索树的根节点；

Step2.在二叉搜索树中左子树的结点小于根结点，因此可以遍历一次得到左子树；

Step3.在二叉搜索树中右子树的结点大于根结点，因此可以继续遍历后序元素得到右子树；

Step4.重复以上步骤递归判断左右子树是不是二叉搜索树，如果都是，则返回true，如果不是，则返回false;

实现：

public static bool VerifySquenceOfBST(int[] sequence, int length){ if (sequence == null || length <= 0) { return false; }

int root = sequence[length - 1];

int i = 0; // 在二叉搜索树中左子树的结点小于根结点 for (; i < length - 1; i++) { if (sequence[i] > root) { break; } } // 在二叉搜索树中右子树的结点大于根结点 int j = i; for (; j < length - 1; j++) { if (sequence[j] < root) { // 如果找到小于根节点直接返回false return false; } } // 判断左子树是不是二叉搜索树 bool leftIsBST = true; if (i > 0) { leftIsBST = VerifySquenceOfBST(sequence, i); } // 判断右子树是不是二叉搜索树 bool rightIsBST = true; if (j < length - 1) { // C#中无法直接操作指针，在C/C++可以直接传递sequence+i int[] newSequence = sequence.Skip(i).ToArray(); rightIsBST = VerifySquenceOfBST(newSequence, length - i - 1); }

return leftIsBST && rightIsBST;}

3单元测试

单元测试用例：

// 10// / \// 6 14// /\ /\// 4 8 12 16[TestMethod]public void SequenceTest1(){ int[] data = { 4, 8, 6, 12, 16, 14, 10 }; bool result = SequenceHelper.VerifySquenceOfBST(data, data.Length); Assert.AreEqual(result, true);}

// 5// / \// 4 7// /// 6[TestMethod]public void SequenceTest2(){ int[] data = { 4, 6, 7, 5 }; bool result = SequenceHelper.VerifySquenceOfBST(data, data.Length); Assert.AreEqual(result, true);}

// 5// /// 4// /// 3// /// 2// /// 1[TestMethod]public void SequenceTest3(){ int[] data = { 1, 2, 3, 4, 5 }; bool result = SequenceHelper.VerifySquenceOfBST(data, data.Length); Assert.AreEqual(result, true);}

// 1// \// 2// \// 3// \// 4// \// 5[TestMethod]public void SequenceTest4(){ int[] data = { 5, 4, 3, 2, 1 }; bool result = SequenceHelper.VerifySquenceOfBST(data, data.Length); Assert.AreEqual(result, true);}

// 树中只有1个结点[TestMethod]public void SequenceTest5(){ int[] data = { 5 }; bool result = SequenceHelper.VerifySquenceOfBST(data, data.Length); Assert.AreEqual(result, true);}

// 错误序列[TestMethod]public void SequenceTest6(){ int[] data = { 7, 4, 6, 5 }; bool result = SequenceHelper.VerifySquenceOfBST(data, data.Length); Assert.AreEqual(result, false);}

// 错误序列[TestMethod]public void SequenceTest7(){ int[] data = { 4, 6, 12, 8, 16, 14, 10 }; bool result = SequenceHelper.VerifySquenceOfBST(data, data.Length); Assert.AreEqual(result, false);}

// 错误序列[TestMethod]public void SequenceTest8(){ bool result = SequenceHelper.VerifySquenceOfBST(null, 0); Assert.AreEqual(result, false);}

测试结果：

测试的结果情况如下图：

Ref参考资料

何海涛，《剑指Offer》

后台回复： 剑指offer，即可获得pdf下载链接哟！

扫码关注EdisonTalk

设为星标，不再失联！

往期推文合集： 2020年上半年推文合集

本文分享自微信公众号 - dotNET跨平台（opendotnet）。
如有侵权，请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”，欢迎正在阅读的你也加入，一起分享。

JZ62 二叉搜索树的第k个结点

题目

给定一棵二叉搜索树，请找出其中的第k小的结点。例如，（5，3，7，2，4，6，8）中，按结点数值大小顺序第三小结点的值为4。

思路

二叉搜索树的中序遍历是有序的

代码

# -*- coding:utf-8 -*-
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    # 返回对应节点TreeNode
    def __init__(self):
        self.res_tin = []

    def KthNode(self, pRoot, k):
        self.printTinNode(pRoot)
        if k==0:
            return None
        elif k<=len(self.res_tin):
            return self.res_tin[k-1]
        else:
            return None

    def printTinNode(self, root):
        if root != None:
            self.printTinNode(root.left)
            self.res_tin.append(root)
            self.printTinNode(root.right)

LeetCode Java刷题笔记—剑指 Offer 54. 二叉搜索树的第k大节点

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

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

简单难度，我们使用反中序遍历，然后遍历一次进行k自减1，当k为0时对应的元素就是第k大的节点。

int k, res;

public int kthLargest(TreeNode root, int k) {
    this.k = k;
    dfs(root);
    return res;
}

private void dfs(TreeNode root) {
    //右递归
    if (root.right != null && k > 0) {
        dfs(root.right);
    }
    //中序递减k并判断是否为0
    if (--k == 0) {
        res = root.val;
        return;
    }
    //左循环
    if (root.left != null && k > 0) {
        dfs(root.left);
    }
}

本文同步分享在博客“刘Java”（CSDN）。
如有侵权，请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”，欢迎正在阅读的你也加入，一起分享。

《剑指offer》链表中倒数第k个节点

本题来自《剑指offer》链表中倒数第k个节点

题目：

　　输入一个链表，输出该链表中倒数第k个结点。

思路：

　　倒数第k个节点，而且只能访问一遍链表，定义两个节点，两者之间相差k个距离，遍历到尾节点，则便找到了倒数k节点了。

　　考虑代码的鲁棒性。代码的鲁棒是指程序能够判断输入是否合乎规范要求，并对不合理的输入给予合理的处理。

　　1.如果传入的根节点是空：直接返回空

　　2.传入的数据少于k个：在遍历前k个节点时候，如果发现为空，则直接返回空

　　3.传入的k为小于或者等于0：直接返回空

　　4.正常的数据，first和second两者相隔k，依次遍历

C++ Code：

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};*/
class Solution {
public:
    ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
        if (!pListHead || k<=0){            //鲁棒性检测，如果头指针为空或者k小于0直接返回空
            return NULL;
        }
        ListNode* first = pListHead;
        ListNode* second = pListHead;
        for (int i=0;i<k;i++){             //第二个节点和第一个节点相隔k个距离
            if (!second){
                return NULL;
            }
            second = second->next;
        }
        while (second){                    //第一个和第二个节点依次遍历，直到尾节点为止
            first = first->next;
            second = second->next;
        }
        return first;                      //第一个节点便是倒数第k个节点
    }
};

Python Code:

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def FindKthToTail(self, head, k):
        # write code here
        if not head or k <=0 :        #如果head为空或者k小于0，直接返回空
            return None
        first,second = head,head
        for i in range(k):         #第二个指针和第一个指针相差k个距离
            if not second :            #考虑，如果个数都小于k，则直接返回空
                return None
            second = second.next
        while second:              #两者同时遍历，直到道尾节点
            first = first.next
            second = second.next
        return first               #第一个节点就是倒数k个节点了

总结：

　　要考虑输入参数的鲁棒性，输入可能取得所有值，比如边界值，要考虑这些值的处理方法。

类似题目：

　　A.求链表的中间节点：如果链表的中间节点总数为奇数，返回中间节点，如果为偶数，返回中间的其中一个。

　　　　定义两个节点，第一个节点first一次跨一步。

　　　　第二个节点second一次跨两步，当该节点是尾节点时候，刚好第一个节点是中间节点。

　　B.判断一个链表是否形成了环形节点

　　　　同上，定义两个指针，慢指针一次跨一步，快的指针一次跨两步，如果快的赶上了慢的，则表明是环形，如果快的指针走到了链表的末尾即为空，则表明不是环形链表。

关于剑指offer和62二叉搜索树的第K个节点的问题就给大家分享到这里，感谢你花时间阅读本站内容，更多关于C#刷剑指Offer | 二叉搜索树的后序遍历序列、JZ62 二叉搜索树的第k个结点、LeetCode Java刷题笔记—剑指 Offer 54. 二叉搜索树的第k大节点、《剑指offer》链表中倒数第k个节点等相关知识的信息别忘了在本站进行查找喔。

本文标签：