513. 找树左下角的值
题目描述
给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。
假设二叉树中至少有一个节点。
解题思路
迭代法简单
class Solution {
public:
int findBottomLeftValue(TreeNode* root) {
deque<TreeNode* > v;
int res=0;
v.push_back(root);
while (!v.empty()) {
res=v.front()->val;
int n = v.size();
for (int i = 0; i < n;i++) {
TreeNode* ptr=v.front();v.pop_front();
if(ptr->left)v.push_back(ptr->left);
if(ptr->right)v.push_back(ptr->right);
}
}
return res;
}
};
递归法
class Solution {
public:
void f(TreeNode*p,int d,int&res,int&resd) {
if(!p)return;
if(d>resd){resd=d;res=p->val;}
f(p->left,d+1,res,resd);
f(p->right,d+1,res,resd);
}
int findBottomLeftValue(TreeNode*root) {
int res=0,resd=0;
f(root,1,res,resd);
return res;
}
};