找树左下角的值( LeetCode 513 )

一、题目描述

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

假设二叉树中至少有一个节点。

二、题目解析

三、参考代码

1、Java 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者:程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 找树左下角的值( LeetCode 513 ):https://leetcode-cn.com/problems/find-bottom-left-tree-value
class Solution {
    public int findBottomLeftValue(TreeNode root) {

        // 设置 res 用来保存输出结果
        int res = 0;

        // 设置一个队列,用来存储二叉树中的元素
        Queue<TreeNode> nodeQueue = new LinkedList<>();

        // 队列添加二叉树的根节点
        nodeQueue.add(root);

        // 遍历队列,直到队列为空,说明访问了二叉树中所有的节点
        while(!nodeQueue.isEmpty()){  

            // 用来记录 nodeQueue 的长度,即每层节点的个数
            int size = nodeQueue.size();  

            // 使用 for 循环,将 nodeQueue 中的元素一个个取出
            for(int i = 0 ; i < size ;  i++ ){   

                // 从 queue 中取出一个节点,此时,nodeQueue 已经抛出了这个节点              
                TreeNode curNode = nodeQueue.poll();  

                // i == 0 时,就说明 node 是这一行最左边的那个节点,记录下节点值
                if( i == 0){
                    res = curNode.val;
                }

                // 判断当前节点的左子节点是否有值,如果有,则添加到 nodeQueue 中
                // 继续搜索下一层的节点
                if(curNode.left != null){
                     nodeQueue.add(curNode.left);
                }

                // 判断当前节点的右子节点是否有值,如果有,则添加到 nodeQueue 中   
                // 继续搜索下一层的节点 
                if(curNode.right != null){
                    nodeQueue.add(curNode.right);
                }    
            }
        }

        // 返回 res
        return res;
    }
}

2、C++ 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者:程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 找树左下角的值( LeetCode 513 ):https://leetcode-cn.com/problems/find-bottom-left-tree-value
class Solution
{
public:
    int findBottomLeftValue(TreeNode *root)
    {

        // 设置 res 用来保存输出结果
        int res = 0;

        // 设置一个队列,用来存储二叉树中的元素
        queue<TreeNode *> nodeQueue;

        // 队列添加二叉树的根节点
        nodeQueue.push(root);

        // 遍历队列,直到队列为空,说明访问了二叉树中所有的节点
        while (!nodeQueue.empty())
        {

            // 用来记录 nodeQueue 的长度,即每层节点的个数
            int size = nodeQueue.size();

            // 使用 for 循环,将 nodeQueue 中的元素一个个取出
            for (int i = 0; i < size; i++)
            {

                // 从 queue 中取出一个节点,此时,nodeQueue 已经抛出了这个节点
                TreeNode *curNode = nodeQueue.front();
                nodeQueue.pop();

                // i == 0 时,就说明 node 是这一行最左边的那个节点,记录下节点值
                if (i == 0)
                {
                    res = curNode->val;
                }

                // 判断当前节点的左子节点是否有值,如果有,则添加到 nodeQueue 中
                // 继续搜索下一层的节点
                if (curNode->left != NULL)
                {
                    nodeQueue.push(curNode->left);
                }

                // 判断当前节点的右子节点是否有值,如果有,则添加到 nodeQueue 中
                // 继续搜索下一层的节点
                if (curNode->right != NULL)
                {
                    nodeQueue.push(curNode->right);
                }
            }
        }

        // 返回 res
        return res;
    }
};


3、Python 代码

# 登录 AlgoMooc 官网获取更多算法图解
# https://www.algomooc.com
# 作者:程序员吴师兄
# 代码有看不懂的地方一定要私聊咨询吴师兄呀
# 找树左下角的值( LeetCode 513 ):https://leetcode-cn.com/problems/find-bottom-left-tree-value
class Solution:
    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:

        # 设置 res 用来保存输出结果
        res = 0

        # 设置一个队列,用来存储二叉树中的元素
        nodeQueue = collections.deque([])

        # 队列添加二叉树的根节点
        nodeQueue.append(root)

        # 遍历队列,直到队列为空,说明访问了二叉树中所有的节点
        while nodeQueue : 

            # 用来记录 nodeQueue 的长度,即每层节点的个数
            size = len(nodeQueue) 

            # 使用 for 循环,将 nodeQueue 中的元素一个个取出
            for i in range(size)  : 

                # 从 queue 中取出一个节点,此时,nodeQueue 已经抛出了这个节点              
                curNode = nodeQueue.popleft()  

                # i == 0 时,就说明 node 是这一行最左边的那个节点,记录下节点值
                if i == 0 : 
                    res = curNode.val


                # 判断当前节点的左子节点是否有值,如果有,则添加到 nodeQueue 中
                # 继续搜索下一层的节点
                if curNode.left :
                     nodeQueue.append(curNode.left)


                # 判断当前节点的右子节点是否有值,如果有,则添加到 nodeQueue 中   
                # 继续搜索下一层的节点 
                if curNode.right :
                    nodeQueue.append(curNode.right)

        # 返回 res
        return res

四、动画理解(没有声音)