遞歸法

題目要求在樹的最后一行找到最左邊的值
用遞歸法如何判斷是最后一行？其實(shí)就是深度最大的葉子節(jié)點(diǎn)一定是最后一行。
如何找最左邊的深度最大的葉子節(jié)點(diǎn)呢?可以使用前序遍歷優(yōu)先在左邊進(jìn)行搜索。
然后記錄深度最大的葉子節(jié)點(diǎn)，此時就是最后一行最左邊的值。

1、確定遞歸函數(shù)的參數(shù)及返回值
參數(shù)必須有要遍歷樹的根節(jié)點(diǎn)，要有int型的變量用來記錄深度最大的葉子節(jié)點(diǎn)。此時就是樹的最后一行最左邊的值

int maxDepth=INT_MIN;//全局變量，用來記錄最大深度 int maxleftValue;//全局變量 最大深度最左邊的數(shù)值。//兩者比較，更新 void traversal(TreeNode* root,int leftDepth)

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

本題我們是要遍歷整個樹找到最深的葉?節(jié)點(diǎn)，需要遍歷整顆樹，所以遞歸函數(shù)沒有返回值。

2、確定終止條件
當(dāng)遇到葉子節(jié)點(diǎn)的時候，就需要統(tǒng)計一下最大深度（遇到葉子節(jié)點(diǎn)就更新最大深度）

if(root->left==nullptr&&left->right==nullptr) {if(leftDepth>maxDepth) {maxDepth=leftDepth;//更新最大深度maxleftValue=root->val;//最大深度最左邊的數(shù)值}return; }

3、確定單層遞歸的邏輯

if(root->left){leftDepth++; //深度加一traversal(root->left,leftDepth);leftDepth--; //回溯，深度減一}if(root->right){leftDepth++;traversal(root->right,leftDepth);leftDepth--;}

完整遞歸代碼：

class Solution{ public:int maxDepth=INT_MIN;int maxleftValue;void traversal(TreeNode* root,int leftDepth){if(root->left==nullptr&&root->right==nullptr){if(leftDepth>maxDepth){ //可避免最大深度相同的情況maxDepth=leftDepth;maxleftValue=root->val;} return; }if(root->left){leftDepth++;traversal(root->left,leftDepth);leftDepth--;}if(root->right){leftDepth++;traversal(root->right,leftDepth);leftDepth--;}}int findBottomLeftValue(TreeNode* root){if(root==nullptr) return 0;traversal(root,1);return maxleftValue;}};

迭代法(最合適)

class Solution { public:int findBottomLeftValue(TreeNode* root) {if(root==nullptr) return 0;queue<TreeNode*> que;que.push(root);int result;while(!que.empty()){int size=que.size();//result=que.front()->val;for(int ii=0;ii<size;ii++){ //開始一層的遍歷TreeNode* node=que.front();que.pop();if(ii==0) result=node->val;//記錄每一層的第一個元素(i==0就表示遍歷到的是每一層的第一個元素)if(node->left) que.push(node->left);if(node->right) que.push(node->right);}}return result;} };

總結(jié)

以上是生活随笔為你收集整理的树左下角的值的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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