昨天没来得及写，今天补上
lc103. 二叉树的锯齿形遍历（MD）
给你二叉树的根节点 root ，返回其节点值的 锯齿形层序遍历 。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：[[3],[20,9],[15,7]]
|
示例 2：
示例 3：
提示：
- 树中节点数目在范围
[0, 2000] 内 -100 <= Node.val <= 100
经典层序遍历
但是要怎么做到在偶数层倒序遍历呢？可以标记一个boolean变量， 用这个变量判断是否要倒序输出
class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if (root == null) {
return res;
}
Queue<TreeNode> que = new LinkedList<>();
que.offer(root);
boolean reverse = false;
while (!que.isEmpty()) {
List<Integer> tmp = new ArrayList<>();
int len = que.size();
for (int i = 0; i < len; i++) {
TreeNode node = que.poll();
tmp.add(node.val);
if (node.left != null) {
que.offer(node.left);
}
if (node.right != null) {
que.offer(node.right);
}
}
if (reverse) {
Collections.reverse(tmp);
}
reverse = !reverse;
res.add(tmp);
}
return res;
}
}
|
lc530. 二叉搜索树的最小绝对差（MD）
给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。
差值是一个正数，其数值等于两值之差的绝对值。
示例 1：
输入：root = [4,2,6,1,3]
输出：1
|
示例 2：
输入：root = [1,0,48,null,null,12,49]
输出：1
|
提示：
- 树中节点的数目范围是
[2, 10^4] 0 <= Node.val <= 10^5
根据二叉搜索树的特性，中序遍历二叉搜索树就能得到一个升序序列，那么根据中序遍历得到的升序序列就能找到最小绝对差
class Solution {
private int pre = -1;
private int res = Integer.MAX_VALUE;
public int getMinimumDifference(TreeNode root) {
dfs(root);
return res;
}
private void dfs(TreeNode root) {
if (root == null) {
return;
}
dfs(root.left);
if (pre == -1) {
pre = root.val;
} else {
res = Math.min(res, root.val - pre);
pre = root.val;
}
dfs(root.right);
}
}
|
lc230. 二叉搜索树中第k小的元素（MD）
给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 个最小元素（从 1 开始计数）。
示例 1：
输入：root = [3,1,4,null,2], k = 1
输出：1
|
示例 2：
输入：root = [5,3,6,2,4,null,null,1], k = 3
输出：3
|
提示：
- 树中的节点数为
n 。 1 <= k <= n <= 1040 <= Node.val <= 104
**进阶：**如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第 k 小的值，你将如何优化算法？
和上一题一样，中序遍历，但是这道题换个做法，我们不用递归了，我们用栈
class Solution {
public int kthSmallest(TreeNode root, int k) {
Stack<TreeNode> stk = new Stack<>();
while (!stk.isEmpty() || root != null) {
while (root != null) {
stk.push(root);
root = root.left;
}
root = stk.pop();
k--;
if (k == 0) {
return root.val;
}
root = root.right;
}
return root.val;
}
}
|
lc98. 验证二叉搜索树（MD）
给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下：
节点的左
子树
只包含
小于
当前节点的数。
节点的右子树只包含 大于 当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
示例 1：
示例 2：
输入：root = [5,1,4,null,null,3,6]
输出：false
解释：根节点的值是 5 ，但是右子节点的值是 4 。
|
提示：
- 树中节点数目范围在
[1, 104] 内 -2^31 <= Node.val <= 2^31 - 1
中序遍历，先考虑左子树和中间节点值的大小关系，如果左子树的值不完全小于中间节点值，那么返回false，否则看右子树
class Solution {
private TreeNode max = null;
public boolean isValidBST(TreeNode root) {
if (root == null) {
return true;
}
boolean left = isValidBST(root.left);
if (!left) return false;
if (max != null && root.val <= max.val) {
return false;
}
max = root;
boolean right = isValidBST(root.right);
return right;
}
}
|
