leetcode513找树左下角的值

解法1：BFS

思路就是层序遍历
用队列记住每层的元素，如果每次记住每层的第一个元素
---->https://programmercarl.com/0102.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E5%B1%82%E5%BA%8F%E9%81%8D%E5%8E%86.html#_102-%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E5%B1%82%E5%BA%8F%E9%81%8D%E5%8E%86

class Solution {
public:
    int findBottomLeftValue(TreeNode* root) {
        int ans = bfs(root);
        return ans;
    }
    int  bfs(TreeNode* root){
        
        if(!root->left&&!root->right){
            return root->val;
        }
        int ans=0;
        queue<TreeNode*> qt;
        qt.push(root);
        while(!qt.empty()){
            int sz=qt.size();
            for (int i = 0; i < sz; ++i) {
                TreeNode* tn=qt.front();
                qt.pop();
                if (tn){
                    if(i==0){
                        ans=tn->val;
                    }
                    if(tn->left){
                        qt.push(tn->left);
                    }
                    if(tn->right){
                        qt.push(tn->right);
                    }

                }
            }
        }
        return ans;
    }
};

解法2：DFS

往左边dfs比右边dfs先完成，如果是同一层的话，左边先得到结果
如果结果不是在同一层，那就是深度更深的先得到结果

class Solution {
public:
    int findBottomLeftValue(TreeNode* root) {
        int ans = 0,h=0,curh=0,curVal=-9999999;
        dfs(root,0,curh,curVal);
        return curVal;
    }
    void dfs(TreeNode* node,int h,int& curh,int& curVal){
        if(!node){
            return;
        }
        h++;
        dfs(node->left,h,curh,curVal);
        dfs(node->right,h,curh,curVal);
        if(h>curh){
            curh=h;
            curVal=node->val;
        }
    }
    
};