博客

/**
 * 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 {
    public int findBottomLeftValue(TreeNode root) {
        //首先这一题使用二叉树的层次遍历来做，并且需要使用两个队列，这样可以区分二叉树每一层的节点。如果只使用一个队列只能实现对一个队列的简单遍历并不能区分节点
        //初始化两个队列，第一个队列初始时存放的时根节点，第二个队列初始时啥也没有
        Queue<TreeNode> queue1 = new LinkedList<>();
        Queue<TreeNode> queue2 = new LinkedList<>();
        int result = root.val;
        queue1.offer(root);
        //需要使用以一个数来记录每层开始时遍历的节点时哪个，这样遍历完所有的节点之后该值存放的就是最下层最左边的元素的值了
        while(!queue1.isEmpty()){
            //层次遍历，每次要做的就是取出第一个队列的值，判断其左右节点是否为空放入第二个队列
            TreeNode node = queue1.poll();
            if(node.left != null){
                queue2.offer(node.left);
            }
            if(node.right != null){
                queue2.offer(node.right);
            }
            //当第一个队列为空时，替换第一个队列为第二个队列的值，初始化第二个队列并且记录下最左边节点的值
            if(queue1.isEmpty()){
                queue1 = queue2;
                queue2 = new LinkedList<TreeNode>();
                if(!queue1.isEmpty()){
                    result = queue1.peek().val;
                }
            }
        }
        return result;
    }
}