面试算法45：二叉树最低层最左边的值

题目

如何在一棵二叉树中找出它最低层最左边节点的值？假设二叉树中最少有一个节点。例如，在如图7.5所示的二叉树中最低层最左边一个节点的值是5。

分析

可以用一个变量bottomLeft来保存每一层最左边的节点的值。在遍历二叉树时，每当遇到新的一层时就将变量bottomLeft的值更新为该层第1个节点的值。当整棵二叉树都被遍历完之后，变量bottomLeft的值就是最后一次更新的值，也就是最后一层的第1个节点的值。

由于用广度优先的顺序遍历二叉树时需要区分不同的层，因此可以用两个队列分别存放不同层的节点，一个队列存放当前遍历层的节点，另一个队列存放下一层的节点。

解

public class Test {public static void main(String[] args) {TreeNode node8 = new TreeNode(8);TreeNode node6 = new TreeNode(6);TreeNode node10 = new TreeNode(10);TreeNode node5 = new TreeNode(5);TreeNode node7 = new TreeNode(7);TreeNode node9 = new TreeNode(9);TreeNode node11 = new TreeNode(11);node8.left = node6;node8.right = node10;node6.left = node5;node6.right = node7;node10.right = node9;node10.right = node11;int result = findBottomLeftValue(node8);System.out.println(result);}public static int findBottomLeftValue(TreeNode root) {Queue<TreeNode> queue1 = new LinkedList<>();Queue<TreeNode> queue2 = new LinkedList<>();queue1.offer(root);int bottomLeft = root.val;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<>();if (!queue1.isEmpty()) {bottomLeft = queue1.peek().val;}}}return bottomLeft;}
}