嘉兴外贸网站建设seo外包公司多少钱

Day123 | 灵神 | 二叉树 | 找树左下角的值

513.找树左下角的值

513. 找树左下角的值 - 力扣（LeetCode）

思路：

初学者可以看灵神视频二叉树的层序遍历【基础算法精讲 13】_哔哩哔哩_bilibili

我的思路就是在每层的循环前加个判断，把res更新队头元素，队头肯定是最左边的

灵神思路是先入队右孩子再入队左孩子，这样最后一个出队的肯定是最左边的

完整代码：

笔者思路：

class Solution {
public:int findBottomLeftValue(TreeNode* root) {queue<TreeNode *> q;int res=0;if(root==nullptr)return res;q.push(root);while(!q.empty()){int size=q.size();vector<int> path;for(int i=size;i>0;i--){TreeNode *t=q.front();q.pop();if(i==size)res=t->val;if(t->left)q.push(t->left);if(t->right)q.push(t->right);}}return res;}
};

灵神代码：

class Solution {
public:int findBottomLeftValue(TreeNode *root) {TreeNode *node;queue<TreeNode *> q;q.push(root);while (!q.empty()) {node = q.front(); q.pop();if (node->right) q.push(node->right);if (node->left)  q.push(node->left);}return node->val;}
};

递归写法：

class Solution {
public:int res;int curdepth=0;void tra(TreeNode *t,int depth){if(t->left==nullptr&&t->right==nullptr){if(depth>curdepth){res=t->val;curdepth=depth;}return;}if(t->left)tra(t->left,depth+1);if(t->right)tra(t->right,depth+1);}int findBottomLeftValue(TreeNode* root) {tra(root,1);return res;}
};