513. 找树左下角的值 – Blog of Aspirer

题目链接：https://leetcode.cn/problems/find-bottom-left-tree-value/

这道题也没做出来，之前的想法是递归遍历，想到把depth传递给递归函数，但是没把最深的depth和val在递归过程中保存下来，而是在递归函数里返回了val，所以就少实现了最深这个条件。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
/*
    void walk(TreeNode* node, int depth, int &curDep, int &curVal) {
        depth++;

        if (node->left) {
            walk(node->left, depth, curDep, curVal);
        }

        if (node->right) {
            walk(node->right, depth, curDep, curVal);
        }

        if (depth > curDep) {
            curDep = depth;
            curVal = node->val;
        }
    }

    int findBottomLeftValue(TreeNode* root) {
        int depth = 0;
        int curDep = 0;
        int curVal = root->val;
        walk(root, depth, curDep, curVal);
        return curVal;
    }
*/

    int findBottomLeftValue(TreeNode* root) {
        int curVal = root->val;
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            auto p = q.front();
            q.pop();
            curVal = p->val;

            if (p->right) {
                q.push(p->right);
            }
            if (p->left) {
                q.push(p->left);
            }
        }

        return curVal;
    }

};

/**

* Definition for a binary tree node.

* struct TreeNode {

* int val;

* TreeNode *left;

* TreeNode *right;

* TreeNode() : val(0), left(nullptr), right(nullptr) {}

* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}

* };

class Solution {

public:

void walk(TreeNode* node, int depth, int &curDep, int &curVal) {

depth++;

if (node->left) {

walk(node->left, depth, curDep, curVal);

}

if (node->right) {

walk(node->right, depth, curDep, curVal);

}

if (depth > curDep) {

curDep = depth;

curVal = node->val;

}

int findBottomLeftValue(TreeNode* root) {

int depth = 0;

int curDep = 0;

int curVal = root->val;

walk(root, depth, curDep, curVal);

return curVal;

}

int findBottomLeftValue(TreeNode* root) {

int curVal = root->val;

queue<TreeNode*> q;

q.push(root);

while (!q.empty()) {

auto p = q.front();

q.pop();

curVal = p->val;

if (p->right) {

q.push(p->right);

}

if (p->left) {

q.push(p->left);

}

return curVal;

}

};