二叉搜索树的第K个节点

问题描述

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

问题分析

二叉搜索树是有序的，因此可以通过中序遍历找到第K个节点
那么问题的关键就是如何实现中序遍历

解题思路1

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
    TreeNode* KthNode(TreeNode* pRoot, int k)
    {
        if(pRoot == NULL || k < 1)
            return NULL;
        return KthNodeCore(pRoot, k);
    }
    
    TreeNode* KthNodeCore(TreeNode* pRoot, int &k){
        TreeNode* 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;
    }
};

解题思路2

//思路：二叉搜索树按照中序遍历的顺序打印出来正好就是排序好的顺序。
//     所以，按照中序遍历顺序找到第k个结点就是结果。
public class Solution {
    int index = 0; //计数器
    TreeNode KthNode(TreeNode root, int k)
    {
        if (root != null) { //中序遍历寻找第k个
            TreeNode node = KthNode(root.left, k);
            if (node != null)
                return node;
            index++;
            if (index == k)
                return root;
            node = KthNode(root.right, k);
            if (node != null)
                return node;
        }
        return null;
    }
}

解题思路3非递归

//非递归   死扣递归很多时候还是有必要的，它不仅是一种优美的思路，简洁的代码，更体现的是对函数不断调入与回溯这一过程的整体把握，基于整个递归程序流程的理解再去写非递归会更简单。递归的过程其实就是函数不断的调入，在计算机中每一个函数都是一个栈帧，函数的调入与完成对应入栈与出栈。
//非递归版中序遍历，可以利用栈来模拟递归遍历，首先根入栈，然后令根节点的左孩子不断入栈直到为空，弹出栈顶，令其右孩子入栈，重复以上操作，直到遍历结束或者访问第k个节点为止。
class Solution {
public:
    TreeNode* KthNode(TreeNode* pRoot, unsigned int k)
    {
        if (!pRoot) return nullptr;
        stack<TreeNode *> res;
        TreeNode* p = pRoot;
        while (!res.empty() || p) {//res是空 and 遍历到空节点
            while (p) {
                res.push(p);
                p = p->left;
            }
            TreeNode* node = res.top();
            res.pop();
            if ((--k) == 0) return node;
            p = node->right;
        }
        return nullptr;
    }
};

注释版

class Solution {
public:
    TreeNode* KthNode(TreeNode* pRoot, int k)
    {
        if (pRoot == NULL || k < 1)
            return NULL;
        //递归实现
        return findKthNode(pRoot, k);
    }
    TreeNode* findKthNode(TreeNode* pRoot, int &k)
    {
        //取一个节点
        TreeNode* node = NULL;
        if (pRoot->left != NULL)
        {
            node = findKthNode(pRoot->left, k);
        }
        
        if (node == NULL)
        {
            //k为1时
            if (k == 1)
            {
                //回溯到当前根节点
                node = pRoot;
            }
            k--;
        }
        if (node == NULL && pRoot->right != NULL)
        {
            node = findKthNode(pRoot->right, k);
        }
        return node;
    }
    
};