算法1

(递归，中序遍历) $O(n)$

考察的是如何中序遍历二叉树
有两种方法，每遍历一个节点，计数器+1和每遍历一个节点，k-1；

Java 代码

    int index = 0; //计数器
    public TreeNode kthNode(TreeNode root, int k)
    {
        if(root != null){ //中序遍历寻找第k个
            TreeNode node = kthNode(root.left,k);
            if(node != null)
                return node;
            index ++;
            if(index == k)
                return root;
            node = kthNode(root.right,k);
            if(node != null)
                return node;
        }
        return null;
    }

Java 代码

    public static int l ;
    public TreeNode kthNode(TreeNode root, int k) {
        if(root==null||k==0)
            return null;
        l = k;
        return kthNodeCore(root);

    }

    public TreeNode kthNodeCore(TreeNode root){
        TreeNode target = null;

        if(root.left!=null){
          target = kthNodeCore(root.left);
        }

        if(target == null){
            if(l==1){
                target = root;
            }
            l--;
        }

        if(target == null&&root.right!=null){
            target = kthNodeCore(root.right);
        }

        return target;
    }