给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。
假设二叉树中至少有一个节点。
方法一：迭代法
class Solution {public: int findBottomLeftValue(TreeNode* root) { //思路：使用队列进行层次遍历，首先先将第一层（根节点）放入队列中 //然后将第二层、第三层等依次放入到队列中 //我们遍历到第几层，队列中存放的就是第几层的节点 //那么如何记录最深层 最左边的节点值的？用ans记录每次执行while语句的第一个节点的值，因为每次 while 执行的是完整的每一层，所以第一个节点的值就是最左边的值 queue que; que.push(root); int ans = 0; int n = 0; while(!que.empty()){ //因为每次 while 执行的是完整的每一层，所以第一个节点的值就是最左边的值 ans = que.front()->val; //n表示当前队列的大小 n = que.size(); //for循环的作用是将当前队列中存放的节点的左右孩子节点（不为空的话），依次将他们放入到队列中 for(int i = 0; i < n; ++i){ TreeNode* temp = que.front(); que.pop(); if(temp->left) que.push(temp->left); if(temp->right) que.push(temp->right); } } return ans; }};
方法二：递归 回溯明显如果需要遍历整棵树，递归函数就不能有返回值。如果需要遍历某一条固定路线，递归函数就一定要有返回值！
class Solution {public: //采用根、左、右的遍历方式，保证左边的遍历完才会遍历到右边 //注意：本题重找出该二叉树的 最底层 最左边 节点的值。此值并不意味着一定是属于左子树的。 //设置全局变量，maxleftLen，maxLeftValue分别表示最大的深度，最大深度最左边的节点值 int maxleftLen = INT_MIN; int maxLeftValue; void traversal(TreeNode* root, int leftLen){ //如果当前节点是叶子节点，并且它的深度是目前遍历到的最大的，那么我们就更新maxleftLen的值，并将当前遍历到的节点的值记为最大深度最左边的值 if(root->left == nullptr && root->right == nullptr){ if(leftLen > maxleftLen){ maxleftLen = leftLen; maxLeftValue = root->val; return; } } //如果当前遍历的节点的存在左孩子，那么就先将最大深度 + 1，然后执行递归函数，当递归函数被 return 后，开始回溯，即找到当前遍历到的节点的上一次递归的节点，向右进行递归 if(root->left){ ++leftLen; traversal(root->left, leftLen); --leftLen; //回溯 } //如果当前遍历的节点的存在右孩子，那么就先将最大深度 + 1，然后执行递归函数，当递归函数被 return 后，开始回溯，即找到当前遍历到的节点的上一次递归的节点，（即上一次递归的节点根、左、右已经完毕）执行 return 语句。 if(root->right){ ++leftLen; traversal(root->right, leftLen); --leftLen; //回溯 } return; } int findBottomLeftValue(TreeNode* root) { traversal(root, 0); return maxLeftValue; }};
隐含回溯的写法
class Solution {public: //采用根、左、右的遍历方式，保证左边的遍历完才会遍历到右边 //注意：本题重找出该二叉树的 最底层 最左边 节点的值。此值并不意味着一定是属于左子树的。 //设置全局变量，maxleftLen，maxLeftValue分别表示最大的深度，最大深度最左边的节点值 int maxleftLen = INT_MIN; int maxLeftValue; void traversal(TreeNode* root, int leftLen){ //如果当前节点是叶子节点，并且它的深度是目前遍历到的最大的，那么我们就更新maxleftLen的值，并将当前遍历到的节点的值记为最大深度最左边的值 if(root->left == nullptr && root->right == nullptr){ if(leftLen > maxleftLen){ maxleftLen = leftLen; maxLeftValue = root->val; return; } } //如果当前遍历的节点的存在左孩子，那么就先将最大深度 + 1，然后执行递归函数，当递归函数被 return 后，开始回溯，即找到当前遍历到的节点的上一次递归的节点，向右进行递归 if(root->left){ traversal(root->left, leftLen + 1); //隐含回溯 } //如果当前遍历的节点的存在右孩子，那么就先将最大深度 + 1，然后执行递归函数，当递归函数被 return 后，开始回溯，即找到当前遍历到的节点的上一次递归的节点，（即上一次递归的节点根、左、右已经完毕）执行 return 语句。 if(root->right){ traversal(root->right, leftLen + 1); //隐含回溯 } return; } int findBottomLeftValue(TreeNode* root) { traversal(root, 0); return maxLeftValue; }};