2019LeetCode暑期打卡活动 Week 3 树专题
LeetCode 98 验证搜索二叉树
1 自下向上的做法
从每个子树中求得最大值和最小值，然后和根节点进行对比
2 自上向下的做法
这个方法好绝呀yxc yyds
根节点(x)的时候，所有值都在[-INF, INF]之间
下到左右子树后，左子树的值必须在[-INF, x)中，右子树的值必须在(x, +INF]中
每向下一层，数值范围缩小，只需要验证是否矛盾即可
Java代码
class Solution {
public boolean isValidBST(TreeNode root) {
return dfs(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
}
public boolean dfs(TreeNode root, long min, long max) {
if (root == null) return true;
if (root.val < min || root.val > max) return false;
return dfs(root.left, min, root.val - 1L) && dfs(root.right, root.val + 1L,max);
}
}
3 利用中序遍历递增序列
中序遍历搜索二叉树是递增序列，所以可以在遍历的时候存一个pre变量，来记录目前遍历到的前一个值，看是否是递增的
Java代码
class Solution {
long pre = Long.MIN_VALUE;
public boolean isValidBST(TreeNode root) {
if (root == null) return true;
if (!isValidBST(root.left)) return false;
if (root.val <= pre) return false;
pre = root.val;
return isValidBST(root.right);
}
}
LeetCode 94 中序遍历二叉树
中序迭代遍历二叉树
步骤
用栈模拟中序遍历
将整棵树的最左边一条链压入栈中
每次去除栈顶元素，如果它有右子树，去除后将右子树压入栈中
Java代码
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
Stack<TreeNode> stk = new Stack<>();
TreeNode cur = root;
while (cur != null || !stk.isEmpty()) { // 如果根节点不空或者栈不空时
while (cur != null) { // 把整个左边的树都加进去
stk.push(cur);
cur = cur.left;
}
cur = stk.pop(); // 输出栈顶元素
res.add(cur.val);
cur = cur.right; // 开始处理右子树
}
return res;
}
}
LeetCode 101 对称的二叉树
步骤
- 根节点不需要管
- 根节点往下，两个根节点的值要相等
- 左边的左子树与右边的右子树对称
- 左边的右子树与右边的左子树对称
Java递归做法
class Solution {
public boolean isSymmetric(TreeNode root) {
if (root == null) return false;
return isSame(root.left, root.right);
}
boolean isSame(TreeNode a, TreeNode b) {
if (a == null || b == null) return a == null && b == null;
if (a.val != b.val) return false;
return isSame(a.left, b.right) && isSame(a.right, b.left);
}
}
迭代做法
可以用中序遍历
1. 先看左边的左子树和右边的右子树是否对称
2. 再看根节点是否相同
3. 再看左边右子树和右边左子树是否对称
左边树遍历顺序 左中右
右边树遍历顺序 右中左
两边同时遍历，对比每一个点
class Solution {
public boolean isSymmetric(TreeNode root) {
if (root == null) return false;
Stack<TreeNode> left = new Stack<>(); // 左子树遍历左中右
Stack<TreeNode> right = new Stack<>(); // 右子树遍历右中左
TreeNode l = root.left, r = root.right; // 两颗左右子树的根节点
while (l != null || r != null || !left.isEmpty() || !right.isEmpty()) {
while (l != null && r != null) {
left.push(l);
right.push(r);
l = l.left;
r = r.right;
}
if (l != null || r != null) return false; // 上面while结束后，有一个为空一个不空则false
l = left.pop();
r = right.pop();
if (l.val != r.val) return false;
l = l.right; // left是左中右
r = r.left; // right是右中左
}
return true;
}
}
LeetCode 105 从前序和中序遍历中重建二叉树
思路
- 从前序遍历中找到当前树的根节点值val = pre[pl]
- 然后从中序遍历中找到val的位置k
- 可知左子树的元素个数为len = k - il
前序 [p_root,p_leftroot,....,p_rightroot,.....]
中序 [i_left,......,i_root,............ i_right]
p_leftroot = p_root + 1
len = i_root - i_left
root = new TreeNode(p[p_root])
root.left = dfs()
root.right = dfs()
Java代码
class Solution {
Map<Integer, Integer> map = new HashMap<>();
int[] preorder;
int[] inorder;
public TreeNode buildTree(int[] _preorder, int[] _inorder) {
preorder = _preorder;
inorder = _inorder;
int i = 0;
for (int a : inorder) map.put(a , i ++ );
return dfs(0, 0, inorder.length - 1);
}
TreeNode dfs(int pl, int il, int ir) {
if (il > ir) return null;
int val = preorder[pl];
TreeNode root = new TreeNode(val);
int k = map.get(val);
int len = k - il;
root.left = dfs(pl + 1, il, k - 1);
root.right = dfs(pl + 1 + len, k + 1, ir);
return root;
}
}
LeetCode 102 层序遍历二叉树
需要注意的点是：
要记录下每层的大小cnt，不能按照q.size()判断，因为q是动态变化的
Java代码
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if (root == null) return res;
Queue<TreeNode> q = new ArrayDeque<>();
q.offer(root);
while (!q.isEmpty()) {
int cnt = q.size();
List<Integer> tmp = new ArrayList<>();
for (int i = 0; i < cnt; i ++ ) {
TreeNode cur = q.poll();
tmp.add(cur.val);
if (cur.left != null) q.offer(cur.left);
if (cur.right != null) q.offer(cur.right);
}
res.add(tmp);
}
return res;
}
}
LeetCode 236 二叉树的公共祖先
返回值的四种情况：
- 如果以root为根的子树总包含p和q的话，则返回它们的最近公共祖先
- 如果只包含p，则返回p
- 如果只包含q，则返回q
- 如果都不包含，则返回null
*
Java代码
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null || root == p || root == q) return root;
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
if (left == null) return right;
if (right == null) return left;
return root;
}
}
LeetCode 543 二叉树的直径
做法
枚举每条路径，更新最大直径
观察：
根据二叉树的特性可知，无论哪条路径都有一个最高点
1
/ \
2 3
/ \
4 5
2是[4 2]和[5 2]的最高点 1是[4 2 1]和[5 2 1][3 1]的最高点
我们枚举每一个最高点，然后后序遍历，找到左边最长和右边最长，然后加和后更新直径
求最大值，就是左右子树的路径长度
Java代码
class Solution {
int res = 0;
public int diameterOfBinaryTree(TreeNode root) {
dfs(root);
return res;
}
int dfs(TreeNode root) {
if (root == null) return 0;
int left = dfs(root.left);
int right = dfs(root.right);
res = Math.max(res, left + right);
return Math.max(left, right) + 1;
}
}
LeetCode 124 二叉树最大路径和
分析
与求最大直径相似，直径题目的每个边权是1，这个题目边权是给定的
枚举所有最高点 从最高点往左走的最大值 + 从最高点往右走的最大值
从最高点走：
1. 向左走 L + x
2. 向右走 R + x
3. 不走 X
dfs的返回值，从root往下走的最大值
出错的点：如果路径最大值小于0，那就不用了
Java代码
class Solution {
int res = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
dfs(root);
return res;
}
int dfs(TreeNode root) {
if (root == null) return 0;
int left = Math.max(0, dfs(root.left));
int right = Math.max(0, dfs(root.right));
res = Math.max(res, left + root.val + right);
return root.val + Math.max(0, Math.max(left, right));
}
}
LeetCode 173 二叉搜索树迭代器
思路
此题要求，平均时间是O(1), 空间是O(h)，所以不能用中序遍历把结点存下来
迭代的方式来求中序遍历，栈的最大深度是最长的一条边，也就是深度，所以满足空间要求
此题考查，用栈的方式来模拟中序遍历，并把该过程的代码拆分成多个部分，封装成几个函数而已
Java代码
class BSTIterator {
Stack<TreeNode> stk = new Stack<>();
public BSTIterator(TreeNode root) {
while (root != null) { // 先把最左边的链加进来
stk.push(root);
root = root.left;
}
}
public int next() {
TreeNode cur = stk.pop(); // 弹出当前的栈顶
int res = cur.val;
cur = cur.right; // 把要弹出元素的所有左边树加进来
while (cur != null) {
stk.push(cur);
cur = cur.left;
}
return res;
}
public boolean hasNext() {
return !stk.isEmpty();
}
}
LeetCode 297 二叉树的序列化和反序列化
思路
序列化和反序列化是一对
序列化的方式有很多种，这里是前序遍历，因为只有前序遍历无法唯一确定一棵二叉树，所以可以加上空节点来唯一确定
前序：根-左-右 空节点 # 结点之间用空格
注意：题目要求不能使用成员变量
Java代码
public class Codec {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
if (root == null) return "# ";
String res = root.val + " " + serialize(root.left) + serialize(root.right);
System.out.println(res);
return res;
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
Queue<String> queue = new LinkedList<>(Arrays.asList(data.split(" ")));
return dfs(queue);
}
TreeNode dfs(Queue<String> queue) {
if (queue.isEmpty()) return null;
String cur = queue.poll();
if ("#".equals(cur)) return null;
TreeNode node = new TreeNode(Integer.parseInt(cur));
node.left = dfs(queue);
node.right = dfs(queue);
return node;
}
}
