LeetCode_61_FindBottomLeftTreeValue

1. question: 找树左下角的值（中等）

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

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/find-bottom-left-tree-value

示例 1:

输入: root = [2,1,3]
输出: 1

示例 2:

输入: [1,2,3,4,null,5,6,null,null,7]
输出: 7

提示:

二叉树的节点个数的范围是 [1,104]
-231 <= Node.val <= 231 - 1

2. answers

这道题的关键点在于左下角，左下角说明是最底层、最左边的节点，注意，不一定是左节点。

最开始的想法是，层序遍历，利用辅助数据结构存储每一层的节点，然后最后一层，取最开始的节点即可。

后来，参考其他题解，发现，其实没必要存储一层节点，只需要存储每层的首节点即可。

之后，参考其他题解，发现，其实也没必要存储节点，在层序遍历的时候，逆序从右到左遍历即可。最后一个节点就是左下角节点。代码如下所示：

public class Solution_0060_02 {

    public static int findBottomLeftValue(TreeNode root) {

        Queue<TreeNode> queue = new LinkedList<>();

        if(root != null) queue.offer(root);

        while(queue.size() >  0) {
            int length = queue.size();

            while(length-- > 0) {

                root = queue.poll();

                // 注意，遍历顺序从右到左
                if(root.right != null) queue.offer(root.right);
                if(root.left != null) queue.offer(root.left);
            }
        }

        // 跳出循环，此时root就是最左侧节点
        return root.val;
    }

    public static void main(String[] args) {

//        TreeNode tn7 = new TreeNode(7);
//        TreeNode tn6 = new TreeNode(6);
//        TreeNode tn5 = new TreeNode(5, tn7, null);
//        TreeNode tn4 = new TreeNode(4);
//        TreeNode tn3 = new TreeNode(3, tn5, tn6);
//        TreeNode tn2 = new TreeNode(2, tn4, null);
//        TreeNode tn1 = new TreeNode(1, tn2, tn3);
//
//        System.out.println(findBottomLeftValue(tn1));

//        TreeNode tn3 = new TreeNode(3);
//        TreeNode tn2 = new TreeNode(1);
//        TreeNode tn1 = new TreeNode(2, tn2, tn3);
//
//        System.out.println(findBottomLeftValue(tn1));

        TreeNode tn1 = new TreeNode(10);
        System.out.println(findBottomLeftValue(tn1));

    }
}

3. 备注

参考力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台 (leetcode-cn.com)，代码随想录 (programmercarl.com)。