【LeetCode-513 | 找树左下角的值】

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>

using namespace std;


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:
    int maxLen = INT_MIN;  // 记录最大深度
    int maxleftValue;  // 最大深度最左节点的数值
    // 1.确定递归函数的入参及返回值
    /*
        因为要遍历整棵树，因此递归函数无返回值
        参数必须有待遍历树的根节点、用于记录最长深度的变量leftLen
    */
    void Traversal(TreeNode* node, int leftLen) {
        // 2.确定递归函数的终止条件
        if(!node->left && !node->right) {
            if(leftLen > maxLen) {
                maxLen = leftLen;
                maxleftValue = node->val;
            }
            return ;
        }
        // 3.确定单层递归逻辑
        if(node->left) {
            leftLen++;
            Traversal(node->left, leftLen);
            leftLen--;
        }

        if(node->right) {
            leftLen++;
            Traversal(node->right, leftLen);
            leftLen--;
        }

        return ;
    }

    int findBottomLeftValue(TreeNode* root) {
        Traversal(root, 0);
        return maxleftValue;
    }
};


/*
    迭代法：利用层序遍历，将最后一层的第一个的元素(即最左边节点)返回即可
*/

class Solution {
public:
    int findBottomLeftValue(TreeNode* root) {
        queue<TreeNode*> que;
        if(root != nullptr) que.push(root);

        int result = 0;
        while(!que.empty()) {
            int size = que.size();
            for(int i = 0; i < size; i++) {
                TreeNode* cur = que.front();
                que.pop();
                if(i == 0) result = cur->val;

                if(cur->left) que.push(cur->left);
                if(cur->right) que.push(cur->right);
            }
        }
        return result;
    }
};