题目

kth-smallest-in-a-best-tree

2. 算法

* 非递归

* 递归

3. 代码

* 非递归

class Solution {

public:

    int kthSmallest(TreeNode* root, int k) {

        int cnt = 0;

        stack<TreeNode*> s;

        TreeNode *p = root;

        while (p || !s.empty()) {

            while (p) {

                s.push(p);

                p = p->left;

            }

            p = s.top(); s.pop();

            ++cnt;

            if (cnt == k) return p->val;

            p = p->right;

        }

        return 0;

    }

};

* 递归

class Solution {

public:

    int kthSmallest(TreeNode* root, int k) {

        return kthSmallestDFS(root, k);

    }

    int kthSmallestDFS(TreeNode* root, int &k) {

        if (!root) return -1;

        int val = kthSmallestDFS(root->left, k);

        if (!k) return val;

        if (!--k) return root->val;

        return kthSmallestDFS(root->right, k);

    }

};