513. 找树左下角的值

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

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

示例 1:

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

示例 2:

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

提示:

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

回溯深度，前中后序都行。无返回值无信息参数。

class Solution {
    // 记录二叉树的最大深度
    int maxDepth = 0;
    // 记录 traverse 递归遍历到的深度
    int depth = 0;
    TreeNode res = null;

    public int findBottomLeftValue(TreeNode root) {
        traverse(root);
        return res.val;
    }

    void traverse(TreeNode root) {
        if (root == null) {
            return;
        }
        
        // 前序遍历位置
        depth++;
        // 下面三块代码的顺序无所谓。如果找到更大的深度，则更新数据
        if (depth > maxDepth) {
            // 到最大深度时第一次遇到的节点就是左下角的节点
            maxDepth = depth;
            res = root;
        }
        traverse(root.left);
        traverse(root.right);
        // 后序遍历位置
        depth--;
    }
}

• 时间复杂度O(n)
• 空间复杂度O(h)

BFS

class Solution {
    public int findBottomLeftValue(TreeNode root) {
        int ret = 0; // 初始化返回值，表示最左下角节点的值
        Queue<TreeNode> queue = new ArrayDeque<>(); // 创建一个队列用于层次遍历（广度优先搜索）
        queue.offer(root); // 将根节点添加到队列中

        // 当队列不为空时，继续遍历
        while (!queue.isEmpty()) {
            TreeNode p = queue.poll(); // 从队列中取出当前节点

            // 先检查右子节点并加入队列，因为要找的是最左下角的节点，
            // BFS的过程中，最后一个遍历到的节点一定是当前层最左边的节点
            if (p.right != null) {
                queue.offer(p.right); // 将右子节点添加到队列中
            }
            // 再检查左子节点并加入队列
            if (p.left != null) {
                queue.offer(p.left); // 将左子节点添加到队列中
            }

            // 更新当前节点的值为最新的节点值，因为我们是从右往左遍历，
            // 最终队列为空时，ret值就是最左下角节点的值。这行代码也可以放在两个if的上面。
            ret = p.val;
        }

        return ret; // 返回最左下角节点的值
    }
}

• 时间复杂度：O(n)，其中 n 是二叉树的节点数目。
• 空间复杂度：O(n)。如果二叉树是满完全二叉树，那么队列 q 最多保存 $⌈n/2⌉=(n+1)/2$ 个节点（因为n一定是奇数）。