题目描述
给定一个二叉树，在树的最后一行找到最左边的值。
题解：
对于二叉树的搜索问题，一般有两种解决方法——深度优先搜索和宽度优先搜索。
因此本题也有对应的两种解法。
解法1：深度优先搜索
由于需要找到树左下找的值，因此可以对二叉树进行中序遍历。首先找到最左侧的叶子节点，后续搜索过程中如果找到深度更大的节点，则进行替换。
void help(TreeNode* root, int d, int& maxd, int& res)
{
if(root == NULL)
{
return;
}
help(root->left, d+1, maxd, res);
if(root->left == NULL && root->right == NULL)
{
if(d > maxd)
{
maxd = d;
res = root->val;
}
}
help(root->right, d+1, maxd, res);
}
int findBottomLeftValue(TreeNode* root) {
int res = 0;
int maxd = -1;
help(root, 0, maxd, res);
return res;
}
解法2：宽度优先搜索
从右到右对二叉树进行层次遍历，最后一个访问到的节点即是树左下角的节点。
int findBottomLeftValue(TreeNode* root) {
queue<TreeNode*> q;
q.push(root);
while(!q.empty())
{
TreeNode* t = q.front();
q.pop();
if(t->right != NULL)
{
q.push(t->right);
}
if(t->left != NULL)
{
q.push(t->left);
}
if(q.empty())
{
return t->val;
}
}
return 0;
}
