LeetCodeHot100_0x06

39. 对称二叉树

求解思路： 学会分解问题，判断对称二叉树，先从最简单三个节点的二叉树开始。
在这里插入图片描述

这个二叉树对称要求：B == C（B完全等于C）
然后将B、C拓展成为二叉树，也就是说，判断二叉树就是判断二叉树的左右子树是否对称。
而左右子树对称的条件有：

根节点相同
左树的左子树与右树的右子树相同
左树的右子树与右树的左子树相同

【递归法】

class Solution {public boolean isSymmetric(TreeNode root) {// 递归法 --- 如何对称？// 问题分解：两个树（子树）什么情况互为镜像？// 1. 根节点具有相同的值// 2. 每个树的右子树都与另一树的左子树镜像对称return check(root.left,root.right);}public boolean check(TreeNode p,TreeNode q) {if(p==null && q==null) return true;  // 两个空树对称if(p==null || q==null) return false; // 一个空树与一个非空树不对称// 满足对称需要三个条件//1. 根相同 p.val = q.val//2. 左:左子树 == 右：右子树//3. 左:右子树 == 右：左子树return p.val == q.val && check(p.left,q.right) && check(p.right,q.left);}
}

40. 二叉树的直径

求解思路： 学会分解问题求二叉树的直径它由三部分组成：

当前节点长度1 + 左子树最大长度len1 + 右子树最大长度len2
当然，这个当前节点未必是根节点，很简单理解，看下图：明显B作为根的时候才有最长长度：FCBDE。所以我们还需要遍历所有节点。

【递归法】思路：遍历所有节点，维护最大长度。

class Solution {public int res = 1; // 答案（不要加static）public int diameterOfBinaryTree(TreeNode root) {// 如果这题换到图，可以用两遍DFS来解决，第一遍从根节点出发，找到最远的节点A// 第二遍从A出发，找距离A最远的点。通过这两边DFS就能找到树的直径了。// 当然这题由于树的结构和图有区别，属于还有第二种思路// 从根节点开始，去记录节点的左子树深度与右子树深度之和，遍历节点的过程中更新最大。solve(root);return res - 1;}public int solve(TreeNode node) {if(node == null) {return 0;}// 这个+1表示当前节点，它是链接左右子树必须经过的节点// 更新最大值int L = solve(node.left);int R = solve(node.right);res = Math.max(res,L+R+1);// 以当前节点为根节点的子树的最大深度return Math.max(L,R) + 1;   }
}

41. 二叉树的层序遍历

求解思路： 层序遍历就是一层一层去读，所以跟图论里的广度优先搜索很像，所以这题我们也可以利用广度优先搜索去做。
【B站代码随想录视频解释】

但是又考虑到，对于同一层的节点，图可以很方便的直接遍历到，但是树结构在遍历左节点的时候是遍历不了右节点的。所以我们需要思考如何记录每一层的元素个数？

可以利用队列来做，需要记录队列大小。具体的思考：

第一轮将根节点放入队列，此时队列长度为1，所以我们只需要进行一次取元素，取到的值放在第一层中，然后将左右节点加入队列。
第二轮由于左右节点的加入，所以此时队列长度为2，也就是第二层有两个元素，所以我们取两次，取到的值加入第二层，然后将左右节点入队
第三轮由于第二层新加入了4个元素，所以此时的长度为4，也就是第三层有4个元素，取4次。以此类推

【BFS广度搜索法】

class Solution {private List<List<Integer>> res = new ArrayList<>();public List<List<Integer>> levelOrder(TreeNode root) {// BFS广度遍历if(root == null) {return res;}BFS(root);return res;}public void BFS(TreeNode root) {//1. 定义队列Queue<TreeNode> queue = new LinkedList<>();//2. 将根节点加入队列queue.offer(root);//3. 进行遍历while(!queue.isEmpty()) {// 3.1 存储遍历当层的列表List<Integer> ans = new ArrayList<>();// 3.2 记录当前队列的长度，也就是上一层的元素个数// 因为队列的长度会不断改变的，但是你如何知道每一层需要弹出几个元素呢？就需要记录一下int NodeCnt = queue.size();for(int i=1;i<=NodeCnt;i++) { // 当前层需要弹出的元素个数 NodeCnt 个//3.3 开始弹出当前层元素TreeNode node = queue.poll();//3.4 把它加入到当前层列表ans.add(node.val);//3.5 将子节点加入到队列if(node.left != null) queue.offer(node.left);if(node.right != null) queue.offer(node.right);}//3.6 将当前层结果保存到resres.add(ans);}}
}

42. 将有序数组转换成二叉搜索树（不会）

求解思路： 二叉搜索树的特征是左边的值小于根，而右边的值大于根。恰巧题目给的是一个有序数组。所以为了平衡，我们可以直接选择中间的节点作为根节点，那这么一来，两边的结点数大致相同。

那如何确定根节点的子节点的值呢？将数组一分为二，前半部分归属于左子树，那按同样的思路，从前半部分中找到中间节点作为新的根节点。右边也是这样操作。

class Solution {public TreeNode sortedArrayToBST(int[] nums) {// 二叉搜索树的构造方式// 目标：二叉搜索树的中序遍历是升序// 题目相当于给了一个中序遍历结果让我们构造二叉树return helper(nums,0,nums.length-1);}/*** 递归思路：每次都选择中间节点作为根节点。左右孩子节点分而治之*/public TreeNode helper(int[] nums, int left, int right) {if(left > right) return null;// 总是选择中间位置靠左边的数字作为根节点，这样两边元素相对平衡int mid = (left + right) / 2;TreeNode root = new TreeNode(nums[mid]);root.left = helper(nums,left,mid-1);root.right = helper(nums,mid+1,right);return root;}
}

43. 验证二叉搜索树

求解思路： 这题吸取上一题教训，思考递归解法。二叉搜索树的判断条件可以拆解三步：

根节点的值大于左子节点的值 && 小于右子节点的值
当前节点的左子树中不能存在比当前节点值还大的值
当前节点的右子树中不能存在比当前节点值还小的值

那么，如何在递归中判断上述步骤呢? 可以定义一个最大边界upper 和最小边界lower，其中：

最大边界upper表示左子树中最大值不能超过的大小，由左子树更新而维护
最小边界lower表示右子树中最小值不能小于的大小，由右子树更新而维护

class Solution {public boolean isValidBST(TreeNode root) {return helper(root,null,null);}public boolean helper(TreeNode root,Integer lower,Integer upper) { // lower、upper表示区间限制if(root == null) return true; int val = root.val;if(lower != null && val <= lower) return false; // 右子树中存在值比目标值（父节点）小if(upper != null && val >= upper) return false; // 左子树中存在值比目标值（父节点）大if(!helper(root.left,lower,val))  return false; // 检查左子树，所有节点的值必须小于当前节点值 更新upper为当前值if(!helper(root.right,val,upper)) return false; // 检查右子树，所有节点的值必须大于当前节点值 更新lower为当前值return true;}
}

44. 二叉搜索树中第K小的元素

求解思路： 二叉搜索树的特点是中序遍历是升序序列，也就是说，这一天可以转换成求二叉树中序遍历中第k个遍历到的元素。那么我们回顾二叉树的中序遍历方法，选择栈模拟方式去记录即可。

class Solution {public int kthSmallest(TreeNode root, int k) {// 利用中序遍历结果找第k个元素Stack<TreeNode> stack = new Stack<>();TreeNode curr = root;int cnt = 0;int res = 0;while(curr != null || !stack.isEmpty()) {// 遍历左子树while(curr != null) {stack.push(curr);curr = curr.left;}// 访问中间节点curr = stack.pop();cnt++;if(cnt == k) {res = curr.val;break;}// 访问右子树curr = curr.right;}return res;}
}

45. 二叉树的右视图

求解思路： 右视图有一个特点，就是每一层只有最‘右边’的元素才会被看到。这样其实就和前面刷的二叉树的层序遍历联动了。我们只需要再层次遍历的过程记录每一层的最后一个元素即可解决这一问题。

class Solution {public List<Integer> rightSideView(TreeNode root) {if(root == null) return new ArrayList<>();// 采用广度搜索，每一层只取最后一个值，就是右视图能看到的// 1// 2 3   选3// 4     选4// 5     选5// 那这一题又和前面的二叉树的层序遍历联动起来了。那就来复习一下吧！Queue<TreeNode> queue = new LinkedList<>(); // 存储队列List<Integer> res = new ArrayList<>();      // 存储答案queue.offer(root);while(!queue.isEmpty()) {int size = queue.size();for(int i=1;i<=size;i++) {TreeNode curr = queue.poll();if(i == size) { // 当前层的最后一个元素res.add(curr.val);}if(curr.left != null) queue.offer(curr.left);if(curr.right != null) queue.offer(curr.right);}} return res;}
}

46. 二叉树展开为链表

求解思路： 这题没想明白，但是看了大佬的题解后恍然大悟。由于题目要求right连接下一个节点，那么我们就不断向右遍历，如果遇到当前节点存在左节点的，将它接到当前节点的右节点，而当前节点的右节点接到现右节点的右边。挺抽象？画图理解：
在这里插入图片描述

class Solution {public void flatten(TreeNode root) {if(root == null) return;TreeNode curr = root;while(curr != null) {if(curr.left == null) {curr = curr.right;  // 不用处理}else {//1. 先找到左子树的最右节点，用来衔接右子树TreeNode leftTree = curr.left;while(leftTree.right != null) {leftTree = leftTree.right;}// 2.原右子树接到左子树的最右节点leftTree.right = curr.right;// 3.原左子树接到右子树的位置curr.right = curr.left;curr.left = null;// 4. 下一个右节点curr = curr.right;}}}
}

47. 从前序与中序遍历构造二叉树

求解思路： 出息了，这题一拿到题目马上就想到分治写法了，靠着肌肉记忆把基本框架搭建起来了。美中不足的是在找第一个未被标识的前序节点时，用了遍历。仔细想其实用一个变量记录就行了。这题的思路是哈希 + 分治
具体的：

先序数组反映的是：根左右
中序数组反映的是：左根右
那么我们每一轮都从先序中取第一个没有被标识的节点作为根！
然后以根节点在中序数组的位置作为左右子树的划分点！
进行左右子树的分治
左右子树分治的结果分别作为Root的左子树和右子树

【哈希 + 分治法】

class Solution {private Set<Integer> hs = new HashSet<>();private int preIndex = 0;public TreeNode buildTree(int[] preorder, int[] inorder) {// 给定 先序+中序 或 后序+中序 可以唯一确定一棵树// 3 9 20 15 7       9 3 15 20 7// 第一轮确定：3为根节点 9为左子树节点组成   15 20 7 为右子树节点组成// 第二轮确定：20为子树根节点 15为左子树节点组成 7 为右子树节点组成// 思路：用哈希表记录已经遍历过的节点，然后分治return solve(preorder,inorder,0,inorder.length-1);}public TreeNode solve(int[]preorder, int[] inorder, int left, int right) {if(left > right) return null;//1. 先取第一个未被标识过的前序节点作为本轮的根节点int temp = preorder[preIndex++];TreeNode currRoot = new TreeNode(temp);hs.add(temp);//2. 在中序中找到分割点位置int mid = -1;for(int i=left; i<=right; i++) {if(inorder[i] == temp) {mid = i;break;}}//3. 分治currRoot.left = solve(preorder,inorder,left,mid-1);currRoot.right = solve(preorder,inorder,mid+1,right);//4. 返回结果return currRoot;}
}

48. 路径总和Ⅲ

求解思路： 从每一个节点出发，不断向下探寻所有解。
【暴力大法】可恶的leetcode最后一个案例居然卡long，但是还是难不倒我暴力大王哈哈哈。

    int res = 0;public int pathSum(TreeNode root, int targetSum) {if(root == null) return 0; // 每个节点都搜一遍的暴力大法 res += dfs(root,(long)targetSum);// 搜索左子节点pathSum(root.left,targetSum);// 搜索右子节点pathSum(root.right,targetSum);return res;}// 以当前节点为根节点，搜索符合题意的路径public int dfs(TreeNode root, long targetSum) {if(root == null) return 0; // 递归终止条件int ans = 0;if(root.val == targetSum) ans++; // 如果相等证明找到了一条目标路径if(root.left != null)ans += dfs(root.left, targetSum-root.val); // 递归左子树下一层if(root.right != null)ans += dfs(root.right, targetSum-root.val); // 递归右子树下一层return ans;}
}

49. 总结

0x06的时间跨度比较大，几乎是一天一两题堆起来的。上周末有考证所以找实习、刷题的工作都搁置了。这个星期我争取将第一轮的Hot100完成，并产出我的简历v2。以上都是外话了，复习一下本文学习到的一些解题方法：
这节真是满满的二叉树啊！

对称二叉树
- 这题理解何为对称，即
- 左子树的左节点 = 右子树的右节点
- 左子树的右节点 = 右子树的左节点

二叉树的直径
- 遍历每一个节点，记录左子树深度与右子树深度Max

二叉树层序遍历
- 队列处理，注意记录队列的size作为每一层需要弹出的元素个数

将有序数组转换成二叉搜索树
- 什么是二叉搜索树？严格有：左 < 中 < 右；
- 所以:分而治之，每次取数组的中间元素作为根分割左右子树即可

验证二叉搜索树
- 什么是二叉搜索树？严格有：左 < 中 < 右；
- 可以定义两个两个边界值 upper 和 lower
- upper上边界值：由左子树维护，如果在左子树中发现有元素超过upper，证明不符合二叉搜索树
- lower下边界值：由右子树维护，如果在右子树发现有元素小于lower，证明不符合二叉搜索树