LeetCode513. 找树左下角的值

题目

代码

层次遍历（一）

 1 class Solution {
 2 public:
 3     int getDepth(TreeNode* root){
 4         if(root == NULL) return 0;
 5         return max(getDepth(root->left),getDepth(root->right))+1;
 6     }
 7     int findBottomLeftValue(TreeNode* root) {
 8         if(root == NULL) return 0;
 9         queue<TreeNode*>q;
10         q.push(root);
11         int res = root->val;
12         int depth = getDepth(root);
13         while(!q.empty()){
14             int sum = q.size();
15             depth--;
16             for(int i = 0;i < sum;i++){
17                 auto t = q.front();q.pop();
18                 if(t->left !=NULL){
19                     if(depth==1) {res = t->left->val;break;}
20                     q.push(t->left);
21                 }     
22                 if(t->right != NULL){
23                     if(depth==1) {res = t->right->val;break;}
24                     q.push(t->right);
25                 }
26             }
27         }
28         return res;
29     }
30 };

层次遍历（二）

 1 class Solution {
 2 public:
 3     int findBottomLeftValue(TreeNode* root) {
 4         if(root == NULL) return 0;
 5         queue<TreeNode*>q;
 6         q.push(root);
 7         int res = root->val;
 8         while(!q.empty()){
 9             int sum = q.size();
10             for(int i = 0;i < sum;i++){
11                 auto t = q.front();q.pop();
12                 if(i == 0) res = t->val;
13                 if(t->left !=NULL){
14                     q.push(t->left);
15                 }     
16                 if(t->right != NULL){
17                     q.push(t->right);
18                 }
19             }
20         }
21         return res;
22     }
23 };

递归（深搜）！！！

class Solution {
public:
    int maxDepth = INT_MIN;
    int res;
    void dfs(TreeNode* root,int depth){
        if(root == NULL) return;
        dfs(root->left,depth+1);  //左 隐含着回溯
        //根
        if(root->left == NULL && root->right ==NULL){
            if(depth > maxDepth) {  //只有出现更长的才更新
                maxDepth = depth;
                res = root->val;
            }
        }
        //右  
        dfs(root->right,depth+1); //隐含着回溯
        
    }
    int findBottomLeftValue(TreeNode* root) {
        if(root == NULL) return 0;
        dfs(root,0);
        return res;
    }
};

如何记录最大深度最大的叶子结点？维护一个长度变量记录当前长度，只有比之前长度长才更新。

如何找最左边？前序、中序、后序其实都可以，因为都是左在前，右在后。所以上面的代码可以将根的操作放在任何位置，只要保证先左后右即可。