leetcode 二叉搜索树中第k小的元素 java

中序遍历

1. 定义一个栈，用于存取二叉树中的元素

Deque<TreeNode> stack = new ArrayDeque<TreeNode>();

2. 进入while循环while(! stack.isEmpty()|| root != null){}
3. 将root的左节点入栈，直到root==null

while(root==null){stack.push(root);root= root.left;
}

4. 将栈中的节点取出来，--k；

root = stack.pop();
--k;
if(k==0){
break;

5. 开始取右节点

root = root.right;

6. 最后返回root.val

整体代码：

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public int kthSmallest(TreeNode root, int k) {Deque<TreeNode> stack  = new ArrayDeque<TreeNode>();while(! stack.isEmpty()||root!=null){while(root!=null){stack.push(root);root = root.left;}root = stack.pop();--k;if(k==0){break;}root = root.right;}return root.val;}
}