Tree, Medium
Question
Given a binary tree, find the leftmost value in the last row of the tree.
Example 1:
1 2 3 4 5 6 7 8
|
Input: 2 / 1 3 Output: 1
|
Example 2:
1 2 3 4 5 6 7 8 9 10 11 12
|
Input: 1 / 2 3 / / 4 5 6 / 7 Output: 7
|
Note: You may assume the tree (i.e., the given root node) is not NULL.
Answer
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
|
* Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class { public int findBottomLeftValue(TreeNode root) { int res = 0; if(root == null) return -1; Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); while(!queue.isEmpty()){ int size = queue.size(); for(int i = 0; i < size; i++){ TreeNode node = queue.poll(); if(i == 0) res = node.val; if(node.left != null) queue.offer(node.left); if(node.right != null) queue.offer(node.right); } } return res; } }
|
Time complexity: O(n)
近期评论