小说网站怎么做原创,专门做二手手机的网站,flash网站规划,温州的网站建设公司java算法day16
112 路径总和404 左叶子之和513 找树左下角的值 112 路径总和
题型判定为自顶向下类型#xff0c;并且为路径和类型。 那就套模板。 自顶向下就是从上到下处理#xff0c;那么就是前序遍历的思想。
class Solution {boolean res false;public boolean hasP…java算法day16
112 路径总和404 左叶子之和513 找树左下角的值 112 路径总和
题型判定为自顶向下类型并且为路径和类型。 那就套模板。 自顶向下就是从上到下处理那么就是前序遍历的思想。
class Solution {boolean res false;public boolean hasPathSum(TreeNode root, int targetSum) {//特判if(rootnulltargetSum0){return false;}//递归dfs(root,targetSum);return res;}//递归void dfs(TreeNode root,int targetSum){if(rootnull){return;}//过程就是不断往下递归成功的条件是叶子节点targetSum-root.val;if(root.leftnull root.rightnull targetSum0){res true;}else{//递归左右子树dfs(root.left,targetSum);dfs(root.right,targetSum);}}
}本题得到的知识。 因为我是按模板做的这个题我非常想在遇到结果的时候就立即返回。但是用模板做那肯定会把全局走完。因此新知识就是怎么实现立即返回。
class Solution {public boolean hasPathSum(TreeNode root, int targetSum) {if(rootnulltargetSum0){return false;}return dfs(root,targetSum);}boolean dfs(TreeNode root,int targetSum){if(rootnull){return false;}targetSum-root.val;if(root.leftnull root.rightnull targetSum0){//完全可以直接返回return true;}//核心思想在理解这里return dfs(root.left,targetSum) || dfs(root.right,targetSum);}
}通过这个题我对递归的理解又更近了一步更新我的想法。 return dfs(root.left,targetSum) || dfs(root.right,targetSum); 这里的正确想法是递归左右子树实际上是递归到最左底层后往上回溯一层然后才是去递归右子树。所以根据短路操作碰到返回true那么反馈给上层上层得到这个true就会把还没递归的右子树给短路。实现了建制。要是按我之前的做法回溯的过程每个右子树都是会去递归的。在某些大型树的场景就效率低了。 404 左叶子之和
这题就两个难点左叶子点怎么定义。如果你对什么是左叶子点很清楚那这个题就很容易。
ps千万别层序遍历去做层序遍历根本判别不了叶子节点是左叶子节点还是右叶子节点
1、左叶子点某点的左孩子节点其左孩子节点的左右孩子都为null那么这个节点就是左叶子点。
2、在递归的时候很容易空指针如何解决 用短路操作把容易空指针的提前断掉。
先序遍历的思想
class Solution {int sum 0;public int sumOfLeftLeaves(TreeNode root) {dfs(root);return sum;}void dfs(TreeNode root){if(rootnull){return ;}//这里就是我的短路操作左叶子节点肯定不是往右走的所以只用判左边是否为空。如果左边都为空了那么结果不可能在那边。所以就不用执行后序的操作。if(root.left!nullroot.left.leftnull root.left.rightnull){sumroot.left.val;}dfs(root.left);dfs(root.right);}
}513 找树左下角的值
树左下角的值题目给的定义就是最后一层最左的节点。
所以我当时就立马想到了层序遍历的做法我在迭代每一层的元素的时候每次把每一层的第一个元素的值存下来还是很容易的。因此马上做了出来。
class Solution {public int findBottomLeftValue(TreeNode root) {DequeTreeNode que new ArrayDeque();que.offerLast(root);int res 0;while(!que.isEmpty()){int size que.size();//每次扩展的时候只存第一个扩展节点的值全部处理完结果就是这个for(int i 0;isize;i){TreeNode temp que.pollFirst();//关键就在这每层处理一下第一个节点。if(i0){res temp.val;}if(temp.left!null){que.offerLast(temp.left);}if(temp.right!null){que.offerLast(temp.right);}}}return res;}
}我提交之后发现效率可以说非常的低。
递归解法 要点 1、实际上转化成了找深度最深的节点。 2、由于要保证最左那递归的时候肯定优先递归左边所以可以用先序遍历。
过程中的难点 1、我在过程中老是在想一找到就立刻返回。实际上这是不太现实的。因为路没走完你根本不可能知道哪个节点才是最深的。因此这个过程应该是不断的寻找最深节点一旦找到更深的节点那就应该把该点的值存下来。 2、起点深度怎么定其实无所谓的最重要的是往下迭代深度的过程。所以一开始设置maxDepth-1就行了result0。那么起点就一定要把maxDepth覆盖。
class Solution {int maxDepth -1;int result 0;public int findBottomLeftValue(TreeNode root) {dfs(root,0);return result;}void dfs(TreeNode node,int depth){if(nodenull){return ;}//我一开始从0相当于先走一步了所以都是往下递归才1.if(depthmaxDepth){maxDepth depth;result node.val;}dfs(node.left,depth1);dfs(node.right,depth1);}
}
