题目描述

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

你可以假设树和k都存在，并且1≤k≤树的总结点数。

样例

输入：root = [2, 1, 3, null, null, null, null] ，k = 3

    2
   / \
  1   3

输出：3

算法1

(DFS)

1. 每一层dfs()，就是每一个节点及其左右子树的遍历。第一层，是 2 1 3。第二层，是1 null null，第三层，是 3 null null。
2. 一开始明白算法是什么样，但是对dfs的理解不深，写了3个if，每个都k –，还忘记加引用&。最后直接MLE了。

时间复杂度

$O(n)$

C++ 代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* res;
    TreeNode* kthNode(TreeNode* root, int k) {
        dfs(root, k);
        return res;
    }

    /*
    TreeNode *dfs(TreeNode *r, int &k)
    {
        if(k == 0) return r;
        if(r->left)
        {
            k --;
            dfs(r->left, k);
        }

        if(r)
        {
            k --;
            dfs(r, k);
        }

        if(r->right) 
        {
            k --;
            dfs(r->right, k);
        }

        return r;
    }
    */

    void dfs(TreeNode *r, int &k)
    {
        if(!r) return;
        dfs(r->left, k);

        k --;
        if(!k) res = r;

        dfs(r->right, k);
    }
};

算法2

(DFS、剪枝)

1. 剪枝的思想：只有当k大于0的时候才会去遍历右子树。因为右子树是遍历顺序的最后一个。k=0的时候直接输出答案了，如果是root，就直接输出，不会再遍历右子树。

时间复杂度

$O(n)$

C++ 代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* res;
    TreeNode* kthNode(TreeNode* root, int k) {
        dfs(root, k);
        return res;
    }


    void dfs(TreeNode *r, int &k)
    {
        if(!r) return;
        dfs(r->left, k);

        k --;
        if(!k) res = r;
        else dfs(r->right, k);
    }
};

C++ 代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* res;
    TreeNode* kthNode(TreeNode* root, int k) {
        dfs(root, k);
        return res;
    }


    void dfs(TreeNode *r, int &k)
    {
        if(!r) return;
        dfs(r->left, k);

        k --;
        if(!k) res = r;
        if(k > 0) dfs(r->right, k);
    }
};