Leetcode-513：找树的左下角值

513. 找树左下角的值

题目描述：
给定一个二叉树的根节点root，请找出该二叉树的 最底层 最左边 节点的值。假设二叉树中至少有一个节点。
需要把握的是题中的最左边的意思，因为是最左边，所以按照题目要求我们求的节点不一定就是左叶子节点，也有可能是最深层的一个右叶子，下面是几个例子及其结果

根据上面的图示我们可以很容易的知道求解目标就是树的最深层的最左边节点的值。对于此类的求解问题一般有两个方向：深度优先和广度优先，一般来说对于涉及层次的问题求解来说，广度优先具有更加清晰的逻辑。下面我们分两个角度来分析解决问题。

深度优先DFS（O(N),O(N)）

深度优先我们通过递归以先序遍历为基础来实现。为了方便层次的比较我们使用一个引用形参curdepth来记录已求出的最左边的值所处的层次方便更新迭代。另外使用depth来表示当前节点所处的层次，为了确保回溯的正确性（不干扰其他节点的深度更新），depth需要设为一个普通形参。

class Solution {
    
public:
    // 其中num是需要记录返回的值，depth是当前访问的树结点的深度
    // curdepth是保存的返回值对应的节点的深度
    void getLeft(TreeNode* root, int &num,int depth,int &curdepth){
    
        if(root == nullptr) return;
        // 保存每一层的最左边元素
        if(root->left == nullptr && root->right == nullptr){
    
            // depth>curdepth就说明当前节点是本层最左边的
            if(depth > curdepth){
    
                curdepth = depth;
                num = root->val;
            }
        }
        getLeft(root->left,num,depth+1,curdepth);
        getLeft(root->right,num,depth+1,curdepth); 
    }
    int findBottomLeftValue(TreeNode* root) {
    
        int n = root->val;
        int dep = 0;
        if(!root->left && !root->right) return n;
        getLeft(root,n,1,dep);
        return n;
    }
};

广度优先BFS（O(N),O(1)）

对于广度优先求解问题就比较简单了，只需要在第一次进入新的一层的时候保存此时的队首节点就是本层的最左边元素的节点值。

class Solution {
    
public:
    int findBottomLeftValue(TreeNode* root) {
    
        // 如果只有根节点，返回根结点的值
        if(!root ->left && !root->right) return root->val;
        // 层次遍历
        queue<TreeNode*> que;
        que.push(root);
        // 初始化返回值
        int res = 0;
        // 访问广度遍历队列
        while(!que.empty()){
    
            size_t size = que.size();
            TreeNode* node = nullptr;
            // 取每一层的最左边元素
            res = que.front()->val;
            // 按层处理元素
            while(size--){
    
                node = que.front();
                que.pop();
                if(node->left) que.push(node->left);
                if(node->right) que.push(node->right);
            }
        }
        // 返回结果
        return res;
    }
};