/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
using namespace std;
//#include <stack>;          // std::stack, std::swap(stack)

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param proot TreeNode类 
     * @param k int整型 
     * @return int整型
     */

    int KthNode(TreeNode* proot, int k) {
        // write code here
        //todo K > treeNodeNumber
        if(NULL == proot ){
            return -1;
        }
        
        //stack<TreeNode*> s = new stack<TreeNode*>();
        //stack<TreeNode*> s = new stack<TreeNode*>();
        
        //C++ sytle declaration;
        stack<TreeNode*> s;
        int i =0;
        while( !s.empty()  || proot !=NULL ){
            if( NULL!= proot){
                s.push(proot);
                proot = proot->left;
            }else{
                //已经左到底了
                proot = s.top();//get top
                s.pop();
                //仅仅下面这4行是定制行为
                i++;
                if( k== i)
                {return proot->val;
                }
                proot = proot->right;
            }
        }
        return -1;
    }
};

//参考C++
//https://blog.nowcoder.net/n/465c4a23a0554861a400bce87c2b061b

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param proot TreeNode类 
     * @param k int整型 
     * @return int整型
     */
    int count=0;//标记现在是第几个数
    vector<int> res;
    int KthNode(TreeNode* proot, int k) {
        // write code here
        if (proot==nullptr||k==0) return -1;
        ++count;
        KthNode(proot->left,  k);
        res.push_back(proot->val);
        //if(count==k) return proot->val;
        KthNode(proot->right, k);
        return res.size()>=k?res[k-1]:-1;
    }
};

//非递归版本

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param proot TreeNode类 
     * @param k int整型 
     * @return int整型
     */
    public int KthNode (TreeNode proot, int k) {
        if(proot == null)    return -1;
        //中序遍历，第k个节点
        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.push(proot);
        TreeNode node = proot;
        int i = 0;
        while(!stack.isEmpty()){
            //遍历node下的所有左节点
            while(node.left != null){
                stack.push(node.left);
                node = node.left;
            }
            i++;
            if(i == k)    return stack.pop().val;
            TreeNode tmp = stack.pop();
            //加入右子树
            if(tmp.right != null){
                stack.push(tmp.right);
                node = tmp.right;
            }
        }
        return -1;
    }
}