题解 | #二叉搜索树的第k个结点#

class Solution {
public:
    TreeNode* KthNode(TreeNode* pRoot, int k) {
        TreeNode *pre=pRoot;
        int a=0;
        stack<TreeNode* > s;
        if(pRoot) s.push(pRoot);
        //中序遍历
        while(!s.empty())
        {
            TreeNode *p=s.top();
            if(p->left&&p->left!=pre&&p->right!=pre)//左孩子不为空且左右孩子尚未遍历
                s.push(p->left);
            else if(p->right==pre)//右孩子刚遍历过
            {
                s.pop();
                pre=p;
            }
            else if(!p->left||p->left==pre)//左孩子为空或者左孩子刚被遍历过
            {
                a++;
                if(a==k)
                    return p;
                pre=p;
                if(p->right)
                    s.push(p->right);
                else
                    s.pop();
            }
        }
        return NULL;
    }
};