二叉树的第K个节点（中序遍历递归&非递归）

栈非递归算法：

class Solution {
public:
    TreeNode* KthNode(TreeNode* pRoot, int k) {
        if(!pRoot||k <= 0){ // pRoot为空返回 k<=0 也返回
            return nullptr;
        }
        stack<TreeNode *> s;
        TreeNode *cur = pRoot;
        while(!s.empty()||cur){
            if(cur){
                s.push(cur);
                cur = cur->left;
            }else{
                cur = s.top();
                s.pop();
                if(--k==0){
                    return cur;
                }
                cur = cur->right;
            }
        }
            return nullptr;
   }
};

递归算法：

class Solution {
public:
    int f = 1;
    TreeNode *ans = NULL;
    TreeNode* KthNode(TreeNode* pRoot, int k) {
        if(!pRoot||k<=0)return NULL;
        inOrder(pRoot, k);
        return ans;
    }
    void inOrder(TreeNode *pRoot,int k){
        if(!pRoot)return;
        inOrder(pRoot->left, k);
        if(f++==k)ans= pRoot; // 按照中序遍历顺序进行查找找到赋值
        inOrder(pRoot->right, k);
    }
};