●??513.找树左下角的值
●??112.?路径总和??113.路径总和ii
●??106.从中序与后序遍历序列构造二叉树?105.从前序与中序遍历序列构造二叉树
https://leetcode.cn/problems/find-bottom-left-tree-value/description/
/**
* 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 {
//定义在全局 属性
int maxDepth=Integer.MIN_VALUE;
int result;
public int findBottomLeftValue(TreeNode root) {
//能判断左叶子节点了,那怎么判断最底层的左叶子节点
//那就每次都记录以下当前深度,直到遇到叶子节点,将这个叶子节点深度和定义在全局的叶子节点深度进行比较,如果叶子节点深度大就更新全局的深度变量,然后记录当前左下角的值
//int curDepth;
findCurDepth(root,0);
return result;
}
public void findCurDepth(TreeNode root,int curDepth){
//终止条件
if(root.left==null&&root.right==null){
//比较当前的深度
if(curDepth>maxDepth){
//更新最大深度值
maxDepth=curDepth;
//更新左下角的值
result=root.val;
}
}
if(root.left!=null){
//每次遍历一个节点,深度+1
curDepth++;
findCurDepth(root.left,curDepth);
//函数调用完毕后,全局属性值已经被更新
//这里的深度变量已经用完,我们要让他恢复(回溯)
curDepth--;
}
if(root.right!=null){
curDepth++;
findCurDepth(root.right,curDepth);
curDepth--;
}
}
}
https://leetcode.cn/problems/path-sum/
/**
* 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 boolean hasPathSum(TreeNode root, int targetSum) {
if(root==null){
return false;
}
return curPathSum(root,targetSum-root.val);
}
public boolean curPathSum(TreeNode root,int curSum){
//将现在的cueSum初始化未目标值,后面每遍历一个节点,就让他减下去,如果最终减为0,那么证明这个路径存在
//写终止条件
//当为叶子节点并且curSum减为0
if(root.left==null&&root.right==null&&curSum==0){
return true;
}
//当为叶子节点但是curSum不为0
if(root.left==null&&root.right==null&&curSum!=0){
return false;
}
//每层的遍历
if(root.left!=null){
//将curSum做减掉操作
curSum-=root.left.val;
boolean left=curPathSum(root.left,curSum);
//如果已经找到了路径和为目标值,那么就返回true
if(left){
return true;
}
//如果找不到路径和为目标值,那么就接着下去遍历新的路径,那么在进行新的前需要将curSum回溯到原来的值
//将curSum回溯到原来的值
curSum+=root.left.val;
}
if(root.right!=null){
curSum-=root.right.val;
boolean right=curPathSum(root.right,curSum);
if(right){
return true;
}
curSum+=root.right.val;
}
//以上都不是,那么就返回false
return false;
}
}
https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
/**
* 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 {
//哈希表,保存元素,下标
Map<Integer,Integer> map;
public TreeNode buildTree(int[] inorder, int[] postorder) {
map=new HashMap<>();
for(int i=0;i<inorder.length;i++){
map.put(inorder[i],i);
}
return findNode(inorder,0,inorder.length,postorder,0,postorder.length);
}
public TreeNode findNode(int[] inorder,int inBegin,int inEnd,int[] postorder,int postBegin,int postEnd){
//1.后续数组为0,空节点
//如果后序数组为空,那么就证明没有根节点,也就不存在二叉树,返回null
if(inBegin>=inEnd||postBegin>=postEnd){
//不满足左闭右开,说明没有元素
return null;
}
//2.后序数组最后一个元素为节点元素
//如果不为空,那就定义一个下标保存着最后一个元素下标
//后序数组最后一个元素下标作为根节点
int rootIndex=map.get(postorder[postEnd-1]);
//定义一颗根节点为rootIndex的二叉树
TreeNode root=new TreeNode(inorder[rootIndex]);
//3.寻找中序数组位置作为切割点
//保存中序左子树个数,用来确定后序数列的个数
int lenOfLeft=rootIndex-inBegin;
root.left=findNode(inorder,inBegin,rootIndex,postorder,postBegin,postBegin+lenOfLeft);//左中序,左后序
root.right=findNode(inorder,rootIndex+1,inEnd,postorder,postBegin+lenOfLeft,postEnd-1);//右中序,右后序
return root;
}
}