【LeetCode】513.找树左下角的值

1 问题

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

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

示例 1

示例1

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

示例 2

示例2

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

提示

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

2 解题思路

2.1 BFS

能快速想到利用BFS，可以参阅2.1队列。

将每层遍历完后，取出该层的第一个元素，即为该层最左元素，直到最后一层完成遍历。

2.2 DFS

利用递归，记录每层的深度、或者说层高，这里只要记录到了，就是这层从左到右顺序中的第一个记录值。下一次，如果在同层，就不会更新了。

3 代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    //BFS
    public int findBottomLeftValue2(TreeNode root) {
        int lastLeftMost = root.val;
        Queue<TreeNode> q = new LinkedList();
        TreeNode tmp;
        List<Integer> list = new LinkedList();
        q.add(root);
        q.add(null);

        while (!q.isEmpty()) {
            tmp = q.poll();
            if (null != tmp) {
                list.add(tmp.val);
                if (null != tmp.left) {
                    q.add(tmp.left);
                }
                if (null != tmp.right) {
                    q.add(tmp.right);
                }
            } else if (!list.isEmpty()) {
                //记录本次最左元素值
                lastLeftMost = list.get(0);
                list = new LinkedList();
                q.add(null);
            }
        }
        return lastLeftMost;
    }

    //DFS
    int height = -1;
    int res = 0;

    public int findBottomLeftValue(TreeNode root) {
        dfs(root, 0);
        return res;
    }

    private void dfs(TreeNode root, int level) {
        if (null == root) {
            return;
        }
        //每层的第一次记录
        if (level > height) {
            res = root.val;
            height = level;
        }
        //DFS
        dfs(root.left, level + 1);
        dfs(root.right, level + 1);
    }
}