嗨，大家好，我是袁廚（因為酷愛做飯，所以自己考取了廚師證），之前一直看大家寫的博客，學到了很多東西，然后最近萌生了自己寫的想法，將自己知道的分享給需要的同學，以后每天會為大家分享leetcode精選題目的各種題解和Python, JS, JQ, CSS, PHP, JAVA的一些小Demo，請大家關注我，一起交流學習吧，
513. 找樹左下角的值
- 題目描述
- 層次遍歷（BFS）
- 做題思路
- 題目代碼
- 遞回法
- 做題思路
- 題目代碼
- 總結
題目描述
層次遍歷（BFS）
做題思路
這個方法比較好想到，也比較容易，但是消耗的時間較多，主要思路就是，根據層次遍歷，每次保存每一層的第一個值即可，然后等遍歷完之后輸出該值題目代碼
class Solution {
public int findBottomLeftValue(TreeNode root) {
if(root == null){
return 0;
}
//創建一個佇列，用來保存每一層的數值
Queue<TreeNode> queue = new LinkedList<TreeNode>();
int leftnum = 0;
//入堆疊
queue.offer(root);
//回圈條件
while(!queue.isEmpty()){
int size = queue.size();
//獲取第一個元素，即我們找到的最左邊的元素
leftnum = queue.element().val;
for(int i = 0;i < size ; i++){
//出隊
TreeNode p = queue.poll();
TreeNode left = p.left;
TreeNode right = p.right;
if(left != null){
queue.offer(left);
}
if(right != null){
queue.offer(right);
}
}
}
return leftnum;
}
}
遞回法
做題思路
我們可以需要定義兩個變數，來找到最底層，當達到最底層時，將值賦給 maxlevelvalue也就是我們需要輸出的值， //用來判斷又到達下一層的時候，因為leftlen是會改變的，
//每下一層則會加1.當下到新的一層時則將最左邊的值賦給maxlevelvalue進行輸出，
if(maxlen < leftlen){
maxlen = leftlen;
maxlevelvalue = root.val;
}
題目代碼
class Solution {
int maxlen = 0;
int maxlevelvalue = 0;
public int findBottomLeftValue(TreeNode root) {
if(root == null){
return 0;
}
dfs(root,1);
return maxlevelvalue;
}
public void dfs(TreeNode root,int leftlen){
//葉子節點情況
if(root.left == null && root.right == null){
//更新了一層，重新賦值
if(maxlen < leftlen){
maxlen = leftlen;
maxlevelvalue = root.val;
}
return ;
}
//左節點
if(root.left != null){
leftlen++;
dfs(root.left,leftlen);
//回溯
leftlen--;
}
if(root.right != null){
leftlen++;
dfs(root.right,leftlen);
leftlen--;
}
return ;
}
}
當然這個代碼是可以精簡的，但是就顯示不出來遞回三要素啦，所以為了便于理解，先根據遞回三要素理解完之后再精簡吧，
總結
這個題目是我比較喜歡的，遞回的邏輯比較難想，層序遍歷的話是比較容易的，明天會做一些新的題型，繼續加油！
作者：LeetCode
鏈接：https://leetcode-cn.com/problems/rotate-array/solution/xuan-zhuan-shu-zu-by-leetcode/
來源：力扣（LeetCode）
著作權歸作者所有，商業轉載請聯系作者獲得授權，非商業轉載請注明出處，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/166066.html
標籤：其他
上一篇：C++四個基本準則及其具體體現