找到左下角的值

题目描述

力扣链接🔗

给定一个二叉树，在树的最后一行找到最左边的值。

代码解析

需要注意的是，最左边不代表就是左下角的值，需要深度最大，且最左边的值。

递归法

1. 确认递归的返回值和参数
   由于只需要返回最后左节点的值，所以一个变量即可，返回值为空。本题还需要类里的两个全局变量，maxLen用来记录最大深度，maxleftValue记录最大深度最左节点的数值。
2. 递归中止条件
   当遇到叶子节点时，需要更新最大深度。并获取最大深度最左面的值。
3. 单层逻辑
   在找最大深度的时候，递归的过程中依然要使用回溯。

public int findBottomLeftValue(TreeNode root) {
    maxLeftValue = root.val;
    traverse(root, 0);
    return maxLeftValue;
}
int maxDeep = -1; // 全局变量 记录最大深度
int maxLeftValue = 0; // 全局变量 最大深度最左节点的数值
public void traverse(TreeNode root, int deep) {
    if (root == null) {
        return;
    }
    // 这里有个隐含条件，就是党到达最大深度时，只获取了第一个最左边（因为是前序遍历）
    // 而且使用的也是 > 符号，并没有 >= 符号
    if (root.left == null && root.right == null) {
        if (deep > maxDeep) {
            maxDeep = deep;   // 更新最大深度
            maxLeftValue = root.val;    // 获取最大深度左节点的值
        }
        return;
    }
    if (root.left != null) {
        deep++;
        traverse(root.left, deep);
        deep--;   // 回溯
    }
    if (root.right != null) {
        deep++;
        traverse(root.right, deep);
        deep--;   // 回溯
    }
}

迭代法

层次遍历只需要找到最后一层的第一个节点即可。

/**
 * 层序遍历
 *
 * @param root
 * @return
 */
public int findBottomLeftValue(TreeNode root) {
    if (root.left == null && root.right == null) {
        return root.val;
    }
    Queue<TreeNode> queue = new LinkedList<>();
    int res = 0;
    queue.offer(root);
    while (!queue.isEmpty()) {
        int len = queue.size();
        res = queue.peek().val; // 取每行的第一个节点值，直到最后一行
        while (len > 0) {
            TreeNode node = queue.poll();
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
            len--;
        }
    }
    return res;
}