找樹左下角的值-513

題目描述

給定一個二叉樹的 根節點 root，請找出該二叉樹的 最底層 最左邊 節點的值。

假設二叉樹中至少有一個節點。

解題思路

這道題用層次遍歷的方式來說是比較簡單的，用遞歸的話如果我們看別人的精簡代碼很難看出其中隱藏的細節，這裡遞歸遍歷其實我們用到了回溯的思想，我們直接採用前序遍歷的方式(其實三種遍歷方式都是一樣的)，定義一個max_depth作為參考值記錄當前遍歷子樹的最大深度，如果我們遍歷到了葉子節點而且其深度大於這個max_depth我們就可以進行賦值操作，反之則不用，因為深度沒有它大的話肯定不是最後一層的葉子節點，沒有我們上一次遍歷子樹的層次高，就無需進行賦值操作

代碼實例

層次

import java.util.*; 
class Solution {
    public int findBottomLeftValue(TreeNode root) {
        Deque<TreeNode> deque=new LinkedList<>();
        deque.add(root);
        List<Integer> result=new ArrayList<>();
        // result.add(root.val);
        while(!deque.isEmpty()){
            int size=deque.size();
            for(int i=0;i<size;i++){
                TreeNode temp=deque.pollFirst();
                result.add(temp.val);
                if(temp.right!=null){
                    deque.addLast(temp.right);
                }
                if(temp.left!=null){
                    deque.addLast(temp.left);
                }
            }

        }

        return result.get(result.size()-1);


    }
}

遞歸

import java.util.*;

class Solution {
    int max_depth=Integer.MIN_VALUE;
    int result=0;
    public int findBottomLeftValue(TreeNode root) {
    
        bianli(root,1);
        return result;
    }

    public void bianli(TreeNode root,int depth) {
        if(root.left==null && root.right==null){
            if(depth>max_depth){
                max_depth=depth;
                result=root.val;
            }
        }
        
        if(root.left!=null){
            bianli(root.left,++depth);
        // 回溯的思想，我們要減去depth然後回溯到根節點然後再從1開始去遍歷我們的右子樹
            depth--;
        }

        if(root.right!=null){
            bianli(root.right,++depth);
            depth--;
        }

    }
}