嗨，大家好，我是袁廚（因為酷愛做飯，所以自己考取了廚師證）。之前一直看大家寫的部落格，學到了很多東西。然後最近萌生了自己寫的想法，將自己知道的分享給需要的同學。以後每天會為大家分享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）
著作權歸作者所有。商業轉載請聯絡作者獲得授權，非商業轉載請註明出處。