题目

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

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

示例 1:
image.png

  1. 输入: root = [2,1,3]
  2. 输出: 1

示例 2:
image.png

  1. 输入: [1,2,3,4,null,5,6,null,null,7]
  2. 输出: 7

提示:

  • 二叉树的节点个数的范围是 [1,10^4]

  • -2^31 <= Node.val <= 2^31 - 1

    解题方法

    层序遍历

    层序遍历二叉树的每一层，用最左侧节点值更新返回结果。
    时间复杂度O(n)，空间复杂度O(n)
    C++代码：

    1. /**
    2. * Definition for a binary tree node.
    3. * struct TreeNode {
    4. *     int val;
    5. *     TreeNode *left;
    6. *     TreeNode *right;
    7. *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
    8. *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    9. *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
    10. * };
    11. */
    12. class Solution {
    13. public:
    14.   int findBottomLeftValue(TreeNode* root) {
    15.       queue<TreeNode*> nodes;
    16.       int result = 0;
    17.       if(!root)   return result;
    18.       nodes.push(root);
    19.       while(nodes.size()>0) {
    20.           int size = nodes.size();
    21.           result = nodes.front()->val;
    22.           for(int i=0; i<size; i++) {
    23.               if(nodes.front()->left)     nodes.push(nodes.front()->left);
    24.               if(nodes.front()->right)    nodes.push(nodes.front()->right);
    25.               nodes.pop();
    26.           }
    27.       }
    29.       return result;
    30.   }
    31. };

    DFS

    前序遍历保证首先搜索到每一层最左叶子，判断当前节点是否为叶子节点，记录最左叶子值以及对应深度，若遇见叶子节点且深度大于记录的深度，则更新记录的最左叶子值。
    时间复杂度O(n)， 空间复杂度O(n)
    C++代码：

    /**
* 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 DFS(TreeNode* cur, int& maxval, int& maxlevel, int level) {
      if(!cur) return;
      if(!cur->left && !cur->right) {
          if(level>maxlevel) {
              maxval = cur->val;
              maxlevel = level;
          }
      }
      DFS(cur->left, maxval, maxlevel, level+1);
      DFS(cur->right, maxval, maxlevel, level+1);
  }

  int findBottomLeftValue(TreeNode* root) {
      int maxval = 0;
      int maxlevel = 0;
      DFS(root, maxval, maxlevel, 1);

      return maxval;
  }
};