題目

給定一個二叉樹，在樹的最后一行找到最左邊的值。

遞歸解

左下角要滿足兩個條件：
1、深度最大的葉子結點
2、最左結點：使用前序遍歷，優先左邊搜索。
1、確定遞歸函數的參數和返回值
參數：樹的根結點，maxlen記錄最大深度,maxleftval記錄最大深度最左結點的數值。

int maxlen = 0;		//全局變量，記錄最大深度
int maxleftval;		//全局變量 最大深度最左節點的數值
void traversal(TreeNode* root,int leftlen);

2、確定終止條件
遇到葉子結點，統計一下最大深度

if(root->left == NULL && root->right == NULL)
{if(leftlen > maxlen)		//如果是同一深度則不會進行更新數值{maxlen=leftlen;		//更新最大深度maxleftval = root->val;		//最大深度最左邊的數值}return ;
}

3、確定單層邏輯
和之前的思路一樣，在找最大深度的時候，遞歸過程中依然要使用回溯

//中，不需要操作
if(root->left)
{leftlen++;	//深度+1traversal(root->left,leflen);leftlen--;	//回溯，深度-1
}
if(root->right)
{leftlen++;	//深度+1traversal(root->right,leflen);leftlen--;	//回溯，深度-1
}
return ;

完整代碼

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:int maxlen = -1;		//全局變量，記錄最大深度int maxleftval;		//全局變量 最大深度最左節點的數值void traversal(TreeNode* root,int leftlen){if(root->left == NULL && root->right == NULL){if(leftlen > maxlen)		//如果是同一深度則不會進行更新數值{maxlen=leftlen;		//更新最大深度maxleftval = root->val;		//最大深度最左邊的數值}return ;}//中，不需要操作if(root->left){leftlen++;	//深度+1traversal(root->left,leftlen);leftlen--;	//回溯，深度-1}if(root->right){leftlen++;	//深度+1traversal(root->right,leftlen);leftlen--;	//回溯，深度-1}return ;}int findBottomLeftValue(TreeNode* root) {traversal(root,0);return maxleftval;}
};

如果需要遍歷整棵樹，遞歸函數就不能有返回值。如果需要遍歷某一條固定路線，遞歸函數就一定要有返回值

層序遍歷解

層序遍歷，將每層第一個元素賦值給一個變量result。遍歷所有層，最后的result就是結果

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:int findBottomLeftValue(TreeNode* root) {int result=0;queue<TreeNode*> que;if(root!=NULL) que.push(root);while(!que.empty()){//該層結點元素個數 = 該層隊列元素int size = que.size();//這里要使用固定大小的size，不能使用que.size(),因為在處理中que.size是不斷變化的//將這層元素送入隊列中并依次從隊首向隊尾將元素出隊列，每個元素出隊列的同時又將其不為空的子結點送入隊列for(int i =0;i<size;i++){if(i==0) result = que.front()->val;TreeNode* node = que.front();//將隊首元素送入該層結果que.pop();//將左右孩子結點入隊列，作為下一層的元素if(node->left) que.push(node->left);if(node->right) que.push(node->right);}}return result;}
};