面试题54:二叉搜索树的第k大节点

题目

给定一颗二叉搜索树，请找出其中第k大的节点。例如，在图中的二叉搜索树中，按节点数值大小顺序，第三大节点的值是4.

image.png

解题思路

若按照中序遍历的顺序遍历一颗二叉搜索树，则遍历序列的数值是递增排序的，如图所示的二叉搜索树的中序遍历序列是{2,3,4,5,6,7,8}.
因此，只需用中序遍历算法遍历一颗二叉搜索树，就容易找出第k大节点

代码

1. 采用中序遍历的方式对二叉搜索树进行递归操作。
2. 设置标志节点，遇到一个结点k递减
3. 递归的详细过程(有点乱，不用看)
   target = kthNodeCore(tree->left,k)-->target = kthNodeCore(tree->left->left,k)-->target = kthNodeCore(tree->left->left->left,k).因为tree->left->left->left为空，target = null。遍历到左子树的叶子结点的下一个节点，递归返回到tree->left->left，target = null ，k = 1.递归返回到tree->left，该结点的左子树遍历完毕，遍历右子树target = kthNodeCore(tree->left->right,k)-->kthNodeCore(tree->left->right->left,k)-->kthNodeCore(tree->left->right->right,k)。此时k = 1，其tree指的是tree->left->right即第三个结点。(可能只有我自己知道自己在说什么，大家不用看这段)

class Solution{
public:
    BinaryTreeNode* kthNodeCore(BinaryTreeNode *tree,int& k)
    {
        BinaryTreeNode* target = NULL;
        if(tree->left != NULL)
        {
            target = kthNodeCore(tree->left,k);
        }
        if(target == NULL)
        {
            if(k == 1)
            {
                target = tree;
            }
            k--;
        }
        if(target == NULL && tree->right != NULL)
        {
            target = kthNodeCore(tree->right,k);
        }
        return target;
    }

    BinaryTreeNode* kthNode(BinaryTreeNode *tree,int k)
    {
        if(tree == NULL || k == 0)
        {
            return NULL;
        }
        return kthNodeCore(tree,k);
    }
};

完整代码见Github