513. 找树左下角的值

原题链接：513. 找树左下角的值

solution:
        ① 通过层序遍历

不需要判断是否遍历到最后一层，是需要用一个变量保存每一层的第一个节点的值，当层序遍历结束的时候，变量保存的一定是最后一层的节点值。

class Solution {
public:
    int findBottomLeftValue(TreeNode* root) {
        queue<TreeNode*> que;
        if(root == nullptr) return 0;
        int ret = 0;
        que.push(root);
        while(!que.empty()) {
            int size = que.size();
            for(int i = 0;i < size;i++) {
                auto t = que.front();
                que.pop();
                if(i == 0) ret = t->val;
                if(t->left != nullptr) que.push(t->left);
                if(t->right != nullptr) que.push(t->right);
            }
        }
        return ret;
    }
};

        ② 深度优先搜索

每次优先递归左子树，用一个变量maxdepth保存递归地最大深度，一个变量ret保存左下角的值，当前遍历的深度curdepth大于maxdepth的时候，更新maxdepth和ret，即可。

class Solution {
public:
    int maxdepth = -1;  //保存遍历的最大深度
    int ret = 0;    //返回值
    
    void dfs(TreeNode *root,int curdepth) {
        if(root == nullptr) return;

        //处于叶子节点
        if(root->left == nullptr && root->right == nullptr) {
            if(curdepth > maxdepth) {
                maxdepth = curdepth;
                ret = root->val;
            }
        }
        dfs(root->left,curdepth + 1);
        dfs(root->right,curdepth + 1);
    }

    int findBottomLeftValue(TreeNode* root) {
        dfs(root, 0);
        return ret;
    }
};