leetcode513

题目

513 找树左下角的值
给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。

思路

本地要找出树的最后一行找到最左边的值。此时大家应该想起用层序遍历是非常简单的了，只需要记录最后一行第一个节点的数值就可以了。反而用递归的话会比较难一点（需要递归+回溯寻找最后一层）。

class Solution
{
public:
    int findBottomLeftValue(TreeNode *root)
    {
        std::queue<TreeNode *> que;
        if (root != NULL)
            que.push(root);
        TreeNode *tmp = nullptr;
        while (!que.empty())
        {
            int size = que.size();
            // 这里一定要使用固定大小size，不要使用que.size()，因为que.size是不断变化的
            for (int i = 0; i < size; i++)
            {
                TreeNode *node = que.front();
                que.pop();
                if (i == 0)
                    tmp = node;//指保存一下每层遍历时第一个节点
                if (node->left)
                    que.push(node->left);
                if (node->right)
                    que.push(node->right);
            }
        }
        return tmp->val;//遍历结束,tmp保存的最后一层第一个节点
    }
};