小鸡玩算法-力扣HOT100-二叉树(下)
一.二叉树展开为链表
问题概述：
给你二叉树的根结点root，请你将它展开为一个单链表：
展开后的单链表应该同样使用
TreeNode，其中right子指针指向链表中下一个结点，而左子指针始终为null。展开后的单链表应该与二叉树先序遍历顺序相同。
思路：
如果左边有东西就需要处理，怎么处理呢，就是把右边的移到左边最后1个后面，然后再把左边的移到右边，左边设为null，没东西了就处理下一个。
代码：
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public void flatten(TreeNode root) { TreeNode cur=root; while(cur!=null){ if(cur.left!=null){ TreeNode move=cur.left; while(move.right!=null){ move=move.right; } move.right=cur.right; cur.right=cur.left; cur.left=null; } cur=cur.right; } } }二.从前序与中序遍历序列构造二叉树
问题概述：
给定两个整数数组preorder和inorder，其中preorder是二叉树的先序遍历，inorder是同一棵树的中序遍历，请构造二叉树并返回其根节点。
思路：
前序遍历：根左右 中序遍历：左根右
后序遍历：左右根
模拟构造的过程，先从前序当中获取根，然后拿着根在中序当中一分为二，先对左半部分进行构造，构造完再对右半部分进行构造。preIndex就是一个一个来的，要构造右边的时候，左边构造的过程中已经把preIndex挪到右边对应的位置上了。拿一个分一个。
简单来说就是前序序列一个一个来设置，中序序列只负责框范围，让它退出递归用的。
注：inorderMap=new HashMap<>();preIndex=0;在里面赋值。别在外面赋值。
代码：
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { private Map<Integer,Integer> inorderMap; private int preIndex; public TreeNode buildTree(int[] preorder, int[] inorder) { inorderMap=new HashMap<>(); for(int i=0;i<inorder.length;i++){ inorderMap.put(inorder[i],i); } preIndex=0; return build(preorder,0,preorder.length-1); } private TreeNode build(int[] preorder,int inLeft,int inRight){ if(inLeft>inRight){ return null; } int rootVal=preorder[preIndex]; TreeNode root=new TreeNode(rootVal); int inIndex=inorderMap.get(rootVal); preIndex++; root.left=build(preorder,inLeft,inIndex-1); root.right=build(preorder,inIndex+1,inRight); return root; } }三.路径总和Ⅲ
问题概述：
给定一个二叉树的根节点root，和一个整数targetSum，求该二叉树里节点值之和等于targetSum的路径的数目。
路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
思路：
两数之和。遍历每个节点，以每个节点为开头，向下延申去凑目标值。 dfs(root,target)表示从root这个节点出发，每条路径都必须有root这个节点，因为=dfs(node.left,target-node.val)当中的node.val就是它的影响。所以需要pathSum(root.left,targetSum)和pathSum(root.right,targetSum)
注：用long，只是因为测试用例有个。
代码：
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public int pathSum(TreeNode root, int targetSum) { if(root==null){ return 0; } return dfs(root,targetSum) +pathSum(root.left,targetSum) +pathSum(root.right,targetSum); } private int dfs(TreeNode node,long target){ if(node==null){ return 0; } int count=0; if(node.val==target){ count++; } count+=dfs(node.left,target-node.val); count+=dfs(node.right,target-node.val); return count; } }四.二叉树的最近公共祖先
问题概述：
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
思路：
后序遍历，左右根，左右找，找到两个返回根，找到一个就直接返回那个找到的。
5左边有6，右边有4，所以返回5。如果是2，左边就没有6，就不是。 每次都是向下面挖到底的，比如从根节点3开始，左右开挖
代码：
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ 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&&right!=null){ return root; } if(left!=null){ return left; } return right; } }五.二叉树中的最大路径和
问题概述：
二叉树中的路径被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中至多出现一次。该路径至少包含一个节点，且不一定经过根节点。
路径和是路径中各节点值的总和。
给你一个二叉树的根节点root，返回其最大路径和。
思路：
maxGan()做的事就是找到以node开头的最长（贡献的最大）那只腿，如果贡献度为-1，那还不如没有呢，为0。
代码：
class Solution { private int maxSum=Integer.MIN_VALUE; public int maxPathSum(TreeNode root) { maxGan(root); return maxSum; } private int maxGan(TreeNode node){ if(node==null){ return 0; } int leftGan=Math.max(maxGan(node.left),0); int rightGan=Math.max(maxGan(node.right),0); int newPrice=node.val+leftGan+rightGan; maxSum=Math.max(maxSum,newPrice); return node.val+Math.max(leftGan,rightGan); } }