LeetCode 513 找树左下角的值

513.找树左下角的值

给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。

假设二叉树中至少有一个节点。

1.1 BFS实现

此处的条件实际上可以简化为，先找到最低层的树节点，然后输出最左边的节点

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

1.2 DFS实现

在DFS实现中，对于最低层的最左端节点，一定是当前层第一个被访问的，那么使用一个pair分别记录层数和第一个被访问的节点的数值。（本质上都是暴力法）

class Solution {
public:
    pair<int,int> res={0,0};
    void DFS(TreeNode *node,int depth){
        if(node){
            depth++;
            if(depth>res.first){
                res={depth,node->val};
            }
            DFS(node->left,depth);
            DFS(node->right,depth);
        }
    }
    int findBottomLeftValue(TreeNode* root) {
        DFS(root,0);
        return res.second;
    }
};