剑指offer（62）二叉树第k个节点

一  非递归方式

/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
import java.util.Stack;
public class Solution {
    TreeNode KthNode(TreeNode pRoot, int k)
    {
        if(pRoot == null || k <= 0){
            return null;
        }
        Stack<TreeNode> stack = new Stack<TreeNode>();
        int index = 0;
        while(pRoot != null || !stack.isEmpty()){
            if(pRoot != null){
                stack.push(pRoot);
                pRoot = pRoot.left;
            }else{
                pRoot = stack.pop();
                index++;
                if(index == k){
                    return pRoot;
                }
                pRoot = pRoot.right;
            }
           
            
        }
        return null;
    }

}

二 递归方式

/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    int index = 0;
    TreeNode KthNode(TreeNode root, int k)
    {
        if(root != null){
            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;
    }

}