題目

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

遞歸解

左下角要滿足兩個(gè)條件：
1、深度最大的葉子結(jié)點(diǎn)
2、最左結(jié)點(diǎn)：使用前序遍歷，優(yōu)先左邊搜索。
1、確定遞歸函數(shù)的參數(shù)和返回值
參數(shù)：樹的根結(jié)點(diǎn)，maxlen記錄最大深度,maxleftval記錄最大深度最左結(jié)點(diǎn)的數(shù)值。

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

2、確定終止條件
遇到葉子結(jié)點(diǎn)，統(tǒng)計(jì)一下最大深度

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

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

//中，不需要操作 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; //全局變量 最大深度最左節(jié)點(diǎn)的數(shù)值void traversal(TreeNode* root,int leftlen){if(root->left == NULL && root->right == NULL){if(leftlen > maxlen) //如果是同一深度則不會(huì)進(jìn)行更新數(shù)值{maxlen=leftlen; //更新最大深度maxleftval = root->val; //最大深度最左邊的數(shù)值}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;} };

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

層序遍歷解

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

/*** 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()){//該層結(jié)點(diǎn)元素個(gè)數(shù) = 該層隊(duì)列元素int size = que.size();//這里要使用固定大小的size，不能使用que.size(),因?yàn)樵谔幚碇衠ue.size是不斷變化的//將這層元素送入隊(duì)列中并依次從隊(duì)首向隊(duì)尾將元素出隊(duì)列，每個(gè)元素出隊(duì)列的同時(shí)又將其不為空的子結(jié)點(diǎn)送入隊(duì)列for(int i =0;i<size;i++){if(i==0) result = que.front()->val;TreeNode* node = que.front();//將隊(duì)首元素送入該層結(jié)果que.pop();//將左右孩子結(jié)點(diǎn)入隊(duì)列，作為下一層的元素if(node->left) que.push(node->left);if(node->right) que.push(node->right);}}return result;} };

總結(jié)

以上是生活随笔為你收集整理的LeetCode 513. 找树左下角的值 思考分析的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。