java算法day16

• 112 路徑總和
• 404 左葉子之和
• 513 找樹左下角的值

---

112 路徑總和

題型判定為自頂向下類型，并且為路徑和類型。
那就套模板。
自頂向下就是從上到下處理，那么就是前序遍歷的思想。

class Solution {boolean res = false;public boolean hasPathSum(TreeNode root, int targetSum) {//特判if(root==null&&targetSum==0){return false;}//遞歸dfs(root,targetSum);return res;}//遞歸void dfs(TreeNode root,int targetSum){if(root==null){return;}//過程就是不斷往下遞歸，成功的條件是葉子節點，targetSum-=root.val;if(root.left==null && root.right==null & targetSum==0){res = true;}else{//遞歸左右子樹dfs(root.left,targetSum);dfs(root.right,targetSum);}}
}

本題得到的知識。
因為我是按模板做的，這個題我非常想在遇到結果的時候就立即返回。但是用模板做，那肯定會把全局走完。因此新知識就是怎么實現立即返回。

class Solution {public boolean hasPathSum(TreeNode root, int targetSum) {if(root==null&&targetSum==0){return false;}return dfs(root,targetSum);}boolean dfs(TreeNode root,int targetSum){if(root==null){return false;}targetSum-=root.val;if(root.left==null && root.right==null & targetSum==0){//完全可以直接返回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(root==null){return ;}//這里就是我的短路操作，左葉子節點肯定不是往右走的，所以只用判左邊是否為空。如果左邊都為空了，那么結果不可能在那邊。所以就不用執行后序的操作。if(root.left!=null&&root.left.left==null && root.left.right==null){sum+=root.left.val;}dfs(root.left);dfs(root.right);}
}

---

513 找樹左下角的值

樹左下角的值，題目給的定義就是，最后一層，最左的節點。

所以我當時就立馬想到了層序遍歷的做法，我在迭代每一層的元素的時候，每次把每一層的第一個元素的值存下來還是很容易的。因此馬上做了出來。

class Solution {public int findBottomLeftValue(TreeNode root) {Deque<TreeNode> que = new ArrayDeque<>();que.offerLast(root);int res = 0;while(!que.isEmpty()){int size = que.size();//每次擴展的時候，只存第一個擴展節點的值，全部處理完，結果就是這個for(int i = 0;i<size;i++){TreeNode temp = que.pollFirst();//關鍵就在這，每層處理一下第一個節點。if(i==0){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就行了，result=0。那么起點就一定要把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(node==null){return ;}//我一開始從0相當于先走一步了，所以都是往下遞歸才+1.if(depth>maxDepth){maxDepth = depth;result = node.val;}dfs(node.left,depth+1);dfs(node.right,depth+1);}
}

---