【leetcode】【剑指offer Ⅱ】045. 二叉树最底层最左边的值

问题描述：

• 给定一个二叉树的根节点 root，请找出该二叉树的最底层最左边节点的值。
  • 假设二叉树中至少有一个节点。

核心思路：

• 二叉树基础应用题。
  • bfs 解题，在每一层的开始更新结果，最后一层的更新结果即为最底层最左边节点的值。
  • dfs 解题，先递归进入左子再递归进入右子（如此便可保证最左边节点比右边节点更早被访问），在递归进入过程中传入当前高度层数，与访问过的最高层数比较，对于第一次出现的高度则保存当前节点的值。

代码实现：

• bfs 解法代码实现如下：

  class Solution
  {
  public:
      int findBottomLeftValue(TreeNode* root)
      {
          queue<TreeNode*> q;
          q.push(root);
          int ans;
          TreeNode* tmp;
          while(!q.empty())
          {
              int sz = q.size();
              for(int i = 0; i < sz; ++i)
              {
                  tmp = q.front(); q.pop();
                  if(i == 0) ans = tmp->val;
                  if(tmp->left) q.push(tmp->left);
                  if(tmp->right) q.push(tmp->right);
              }
          }
          return ans;
      }
  };
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23