思路：

看到二叉搜索树一定要想起“中序遍历”

利用一个pre变量，记录前驱节点。

中序遍历一次，就相当于遍历了一个单调数组。

class Solution {// 前驱节点private long pre = Long.MIN_VALUE;public boolean isValidBST(TreeNode root) {if (root == null) {return true;}// 左if (!isValidBST(root.left)) {return false;}// 中（本节点）// 如果违反单调性，向上返回falseif (root.val <= pre) {return false;}// 更新前驱节点pre = root.val;// 右if (!isValidBST(root.right)) {return false;}return true;}
}

思路：

看到二叉搜索树一定要想起“中序遍历”。

中序遍历，相当于用for遍历了一个有序数组。返回数组中索引为k的元素。

class Solution {private int index = 0;private int k;private int target;public int kthSmallest(TreeNode root, int k) {this.k = k;midorder(root);return target;}// 中序遍历，相当于用for遍历了一个有序数组。返回数组中索引为k的元素。private void midorder(TreeNode node) {// 多写一个index>=k，可以提前return，剪枝if (node == null || index >= k) {return;}if (node.left != null) {midorder(node.left);}// 中if (++index == k) {target = node.val;return;}if (node.right != null) {midorder(node.right);}}
}

思路：

先递归到右子树，进入新depth的第一个节点就会是最右边的

class Solution {List<Integer> res = new ArrayList<>();public List<Integer> rightSideView(TreeNode root) {dfs(root, 1);return res;}private void dfs(TreeNode node, int depth) {if (node == null) {return;}// 记录进入这个深度的第一个节点if (depth > res.size()) {res.add(node.val);}// 先递归到右子树，进入新depth的第一个节点就会是最右边的dfs(node.right, depth + 1);dfs(node.left, depth + 1);}}

思路：

也可以用层序遍历解决这道题。迭代法。

//  层序遍历，每层的最后一个元素拿出来。
class Solution {public List<Integer> rightSideView(TreeNode root) {List<Integer> res = new ArrayList<>();if (root == null) {return res;}Deque<TreeNode> que = new ArrayDeque<>();que.offer(root);while (!que.isEmpty()) {int levelCount = que.size();for (int i = 0; i < levelCount; i++) {TreeNode node = que.pop();// 右子树先入队，就是把每层第一个元素拿出来if (node.right != null) {que.offer(node.right);}if (node.left != null) {que.offer(node.left);}// 当i是本层第一个节点的时候，把值加入到res里if (i == 0) {res.add(node.val);}}}return res;}
}