前言
记录LeetCode刷题中遇到的二叉树相关题目，第二篇。第一篇地址
105.从前序与中序遍历序列构造二叉树(每日一题)
前序遍历的访问顺序是先访问根，再访问左子树，再访问右子树
中序遍历的访问顺序是先访问左子树，再访问根，再访问右子树
根据访问顺序的规律我们可以把当前这棵树分为根，左子树，右子树三个部分，如：
前序遍历：12436587
中序遍历：42635187
可以找出当前这棵树的根为1，24365是左子树的部分，87是右子树的部分，怎么知道要这么分？在中序遍历中找到根，也就是1，也就是前序遍历序列的第一个值，的位置就可以了。所以我们可以构造一个根据前序跟中序遍历序列找出根的方法，然后分治，递归，对左右子树的遍历序列调用这个方法就可以
public TreeNode buildTree(int[] preorder, int[] inorder) {
//结束：遍历序列为空时返回空
if(preorder.length == 0) return null;
TreeNode root = new TreeNode(preorder[0]);
for(int i = 0;i < preorder.length;i++){
//在中序遍历序列中找根的位置
if(inorder[i] == preorder[0]){
//找到根的位置后就可以得出左，右子树的遍历序列了
int[] newPre1 = Arrays.copyOfRange(preorder,1,i + 1);
int[] newIn1 = Arrays.copyOfRange(inorder,0,i);
//分解，对左子树部分的遍历序列调用方法的返回结果就是左子树的根
// 对右子树部分的遍历序列调用方法的返回结果就是右子树的根
root.left = buildTree(newPre1,newIn1);
int[] newPre2 = Arrays.copyOfRange(preorder,i + 1,preorder.length);
int[] newIn2 = Arrays.copyOfRange(inorder,i + 1,inorder.length);
root.right = buildTree(newPre2,newIn2);
break;
}
}
return root;
}
106.从中序与后序遍历序列构造二叉树
思路跟105差不多。不同的是，这里根变成了后序遍历的最后一个值；截取左右子树的遍历序列的方式也有一些不同
public TreeNode buildTree(int[] inorder, int[] postorder) {
if(postorder.length == 0) return null;
int l = postorder.length;
TreeNode root = new TreeNode(postorder[l - 1]);
for(int i = 0;i < l;i++){
if(inorder[i] == postorder[l - 1]){
int[] newPost1 = Arrays.copyOfRange(postorder,0,i);
int[] newIn1 = Arrays.copyOfRange(inorder,0,i);
root.left = buildTree(newIn1,newPost1);
int[] newPost2 = Arrays.copyOfRange(postorder,i,l - 1);
int[] newIn2 = Arrays.copyOfRange(inorder,i + 1,l);
root.right = buildTree(newIn2,newPost2);
break;
}
}
return root;
}
257.二叉树的所有路径
采用分治的思想，当前节点应该返回的路径应该是左子树和右子树所有应该返回的路径前面再加一个当前节点的值
public List<String> binaryTreePaths(TreeNode root) {
//递归分治的边界，通常在树中做递归边界都是空节点
if(root == null) return null;
//当前节点没有左右孩子，也就是叶子节点，那么要返回的路径就是只有自己的路径
if(root.left == null && root.right == null){
List<String> res = new ArrayList<>();
res.add(String.valueOf(root.val));
return res;
}
//分治
List<String> leftStrs = binaryTreePaths(root.left);
List<String> rightStrs = binaryTreePaths(root.right);
List<String> all = new ArrayList<>();
//结合分治得到的两个结果为总的结果
if(leftStrs != null){
for(String s : leftStrs){
all.add(root.val + "->" + s);
}
}
if(rightStrs != null){
for(String s : rightStrs){
all.add(root.val + "->" + s);
}
}
return all;
}
100.相同的树
判断两棵树是否相同，先判断根是否相同，然后先判断左子树是否相同，如果左子树不相同，那就可以不用判断右子树是否相同直接返回false，如果左子树也是相同的，那就返回右子树是否相同的结果
public boolean isSameTree(TreeNode p, TreeNode q) {
//防止下面.val和.left .right出现空指针异常，
//所有两棵树可能为null的情况都要先判断
if(p == null && q==null)return true;
if(p== null || q == null) return false;
if(p.val != q.val) return false;
boolean left = isSameTree(p.left,q.left);
if(left == false) return false;
return isSameTree(p.right,q.right);
}
404.左叶子之和
public int sumOfLeftLeaves(TreeNode root) {
if(root == null) return 0;
//如何判断左叶子，从左叶子自身并不能知道它是左叶子，
//只能从父亲节点才能判断
if(root.left != null && root.left.left == null && root.left.right == null){
return root.left.val + sumOfLeftLeaves(root.right);
}
return sumOfLeftLeaves(root.left) + sumOfLeftLeaves(root.right);
}
236.二叉树的最近公共祖先
最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）
两个前提
- 所有 Node.val 互不相同
- p 和 q 均存在于给定的二叉树中
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
//首先找到null时返回null是必然的。然后如果找到了p或q，
//那就返回这个结点，所以写在一起就是下面这句
if(root == p || root == q || root == null) return root;
//分别找左边和右边
TreeNode l = lowestCommonAncestor(root.left,p,q);
TreeNode r = lowestCommonAncestor(root.right,p,q);
//因为p和q一定是存在的，所以要么是一个来自左子树一个来自右子树
//要么是都来自左子树或都来自右子树。反正l跟r肯定不会两个都是null
//如果l跟r都不为null，说明p和q一个来自左子树一个来自右子树，
//那么当前节点就是所求的最近公共祖先
if(l != null && r != null) return root;
//当l不为null，那么r肯定为null，所以p跟q都来自左子树，l为最近公共祖先
if(l != null) return l;
//r不为null时同理
if(r != null) return r;
return null;
}
剑指 Offer 54. 二叉搜索树的第k大节点(每日一题)
二叉树的特征就是传统中序遍历 (即先遍历左子树再遍历根节点再遍历右子树) 的结果为递增序列，所以中序遍历中，越先被遍历到的节点，它在最终得到的遍历序列中的大小排序就越小
这种情况遍历顺序并不利于我们找到第k大节点(但利于找到倒数第k大节点)
解决方法就是对传统的中序遍历做点调整：先遍历右子树，再遍历根节点，再遍历左子树，这样得到的遍历序列就是递减的了，不用遍历整棵树得到完整的遍历序列就能找到第k大节点
class Solution {
//num表示当前遍历到的节点是树中第num大节点，当num == k的时候就说明找到了第k大节点
int num;
int inorder(TreeNode root,int kk){
//只要是找不到都返回-1，所以只要返回了非-1得数据就说明是找到了，一路返回到根节点
if(root == null) return -1;
int r = inorder(root.right,kk);
if(r != -1) return r;
if(num == kk) return root.val;
else num++;
int l = inorder(root.left,kk);
if(l != -1) return l;
return -1;
}
public int kthLargest(TreeNode root, int k) {
num = 1;
return inorder(root,k);
}
}
最终耗时也是0ms
剑指 Offer II 049. 从根节点到叶节点的路径数字之和(每日一题)
递归的思路：对于当前节点，它代表的值就是父节点代表的值乘以10再加上当前节点的值，然后如果当前节点为叶子节点，那就直接返回这个值，否则就向下递归，求左右子树上叶节点代表的数字之和
class Solution {
public int sumNumbers(TreeNode root) {
return sonNumber(0,root);
}
int sonNumber(int parent,TreeNode t){
if(t == null) return 0;
int val = parent * 10 + t.val;
if(t.left == null && t.right == null) return val;
return sonNumber(val,t.left) + sonNumber(val,t.right);
}
}
剑指 Offer 32 - III. 从上到下打印二叉树 III(每日一题)
在层次遍历二到基础上，加一个当前层次要从左往右还是从右往左的布尔标记，如果是从左往右，就要按照尾插的方式插入列表；如果是从右往左，就按照头插的方式插入列表，得到的列表就是当前这一层的遍历序列
public List<List<Integer>> levelOrder(TreeNode root) {
if(root == null) return new LinkedList<>();
List<List<Integer>> res = new LinkedList<>();
Deque<TreeNode> queue = new LinkedList<>();
queue.addLast(root);
//right标记，true时为从左向右；false时从右往左
boolean right = true;
while(!queue.isEmpty()){
int size = queue.size();
LinkedList<Integer> l = new LinkedList<>();
for(int i = 0;i < size;i++){
TreeNode poll = queue.poll();
if(poll.left != null) queue.addLast(poll.left);
if(poll.right != null) queue.addLast(poll.right);
//从左往右时尾插，否则头插
if(right) l.addLast(poll.val);
else l.addFirst(poll.val);
}
res.add(l);
//right取反
right = !right;
}
return res;
}
面试题 04.04. 检查平衡性(每日一题)
检查平衡性，就是要通过左右子树的高度差来判断，所以思路就是求深度，但又不需要对每个节点都去求深度，只要找到一个高度差大于1，就可以得出整棵树是不平衡的结论了
class Solution {
int depth(TreeNode t){
if(t == null) return 0;
int l = depth(t.left);
if(l == -1) return -1; //----|
int r = depth(t.right); // |-->左右子树有一个返回了-1，根节点就可以直接返回-1
if(r == -1) return -1; //----|
if(Math.abs(l - r) > 1) return -1; //当前根节点的子树不平衡，返回-1
return Math.max(l,r) + 1; //当前子树是平衡的，就返回深度
//可以看出来，只要找到了一个高度差大于1，返回值-1就会一直沿着节点往上一直返回到最上面根节点，避免了其它求深度的操作
}
public boolean isBalanced(TreeNode root) {
if(depth(root) == -1) return false;
return true;
}
}
