Java日常练习题,每天进步一点点(57)

题目：求一个二叉树的右下角结点的值。

思路

先按照层次遍历的方式，遍历整棵树，将每一层最后一个结点的值保存下来，最后返回最后一层的最后一个结点的值即可。

代码实现

private int lastVal = 0;
public int findBottomLeftValue(TreeNode root) {
    // 用队列保存待遍历的结点
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while(!queue.isEmpty()) {
        int size = queue.size();
        lastVal = queue.peek().val;
        for(int i=0; i<size; i++) {
            TreeNode node = queue.poll();
            if(node.right != null) {
                queue.offer(node.right);
            }
            if(node.left != null) {
                queue.offer(node.left);
            }
        }
    }
    return lastVal;
}

示例说明

以如下的二叉树为例：

    1
   / \
  2   3
 /   / \
4   5   6

按照层次遍历的方式，遍历完整棵树的顺序为1->2->3->4->5->6。在遍历到最后一层时，由于每层的结点都是从左到右遍历的，所以在遍历到这一层时，最后一个结点一定是最右边的结点，即结点6。因此，最后输出的结果为6。