小鸡玩算法-力扣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 curroot; while(cur!null){ if(cur.left!null){ TreeNode movecur.left; while(move.right!null){ movemove.right; } move.rightcur.right; cur.rightcur.left; cur.leftnull; } curcur.right; } } }二.从前序与中序遍历序列构造二叉树问题概述给定两个整数数组preorder和inorder其中preorder是二叉树的先序遍历inorder是同一棵树的中序遍历请构造二叉树并返回其根节点。思路前序遍历根左右 中序遍历左根右后序遍历左右根模拟构造的过程先从前序当中获取根然后拿着根在中序当中一分为二先对左半部分进行构造构造完再对右半部分进行构造。preIndex就是一个一个来的要构造右边的时候左边构造的过程中已经把preIndex挪到右边对应的位置上了。拿一个分一个。简单来说就是前序序列一个一个来设置中序序列只负责框范围让它退出递归用的。注inorderMapnew HashMap();preIndex0;在里面赋值。别在外面赋值。代码/** * 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 MapInteger,Integer inorderMap; private int preIndex; public TreeNode buildTree(int[] preorder, int[] inorder) { inorderMapnew HashMap(); for(int i0;iinorder.length;i){ inorderMap.put(inorder[i],i); } preIndex0; return build(preorder,0,preorder.length-1); } private TreeNode build(int[] preorder,int inLeft,int inRight){ if(inLeftinRight){ return null; } int rootValpreorder[preIndex]; TreeNode rootnew TreeNode(rootVal); int inIndexinorderMap.get(rootVal); preIndex; root.leftbuild(preorder,inLeft,inIndex-1); root.rightbuild(preorder,inIndex1,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(rootnull){ return 0; } return dfs(root,targetSum) pathSum(root.left,targetSum) pathSum(root.right,targetSum); } private int dfs(TreeNode node,long target){ if(nodenull){ return 0; } int count0; if(node.valtarget){ count; } countdfs(node.left,target-node.val); countdfs(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(rootnull||rootp||rootq){ return root; } TreeNode leftlowestCommonAncestor(root.left,p,q); TreeNode rightlowestCommonAncestor(root.right,p,q); if(left!nullright!null){ return root; } if(left!null){ return left; } return right; } }五.二叉树中的最大路径和问题概述二叉树中的路径被定义为一条节点序列序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中至多出现一次。该路径至少包含一个节点且不一定经过根节点。路径和是路径中各节点值的总和。给你一个二叉树的根节点root返回其最大路径和。思路maxGan()做的事就是找到以node开头的最长贡献的最大那只腿如果贡献度为-1那还不如没有呢为0。代码class Solution { private int maxSumInteger.MIN_VALUE; public int maxPathSum(TreeNode root) { maxGan(root); return maxSum; } private int maxGan(TreeNode node){ if(nodenull){ return 0; } int leftGanMath.max(maxGan(node.left),0); int rightGanMath.max(maxGan(node.right),0); int newPricenode.valleftGanrightGan; maxSumMath.max(maxSum,newPrice); return node.valMath.max(leftGan,rightGan); } }