剑指offer62二叉搜索树的第k个结点

剑指offer62

1.递归中序遍历 计数
个人答案

class Solution {
public:
    int num=0; //遍历计数
    TreeNode* ret=nullptr; //最终节点存入
    TreeNode* KthNode(TreeNode* pRoot, int k) {
        if(k<=0||!pRoot)
            return nullptr;
        midTraverse(pRoot,k);
        return ret;
    }

    void midTraverse(TreeNode* pRoot,int k)  //中序遍历
    {
        if(num==k) //如果已经找到，再次递归进去提前剪枝，避免后续递归
            return;
        if(!pRoot)
            return;
        midTraverse(pRoot->left,k);
        ++num;
        if(num==k)
            ret=pRoot;
        midTraverse(pRoot->right,k);
    }
};

2、栈+中序遍历，用栈模拟递归
个人答案

 //以某子树根节点为当前节点，先压入当前节点，然后压入左子树的根节点，处理完左子树，
    //再处理该节点，再压入右子树根节点,处理右子树，处理完右子树后整个子树已经被弹出了，返回到
    //该节点的父节点(该节点为父节点的左孩子)，然后处理父节点的右子树....
    TreeNode* KthNode(TreeNode* pRoot, int k) {
        stack<TreeNode*>st;
        while(pRoot||st.size()!=0)
        {
            //压入到左孩子为空的某节点，以此节点为当前节点处理该节点和该节点的右子树情况
            while(pRoot) 
            {
                st.push(pRoot);
                pRoot=pRoot->left;
            }
            pRoot=st.top(); //弹出当前节点
            st.pop();
            if(--k==0) return pRoot; //print等处理当前节点
            pRoot=pRoot->right; //当前节点的右孩子置为当前节点，存在则压入
            }
        return nullptr;
    }