[LeetCode] 513. Find Bottom Left Tree Value
Given a binary tree, find the leftmost value in the last row of the tree.
Example 1:
Input: 2 / \ 1 3 Output: 1
Example 2:
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.
Thought process:
BFS. Level order traversal. Use a variable to keep track of the first node of each level.
Solution 1 (BFS):
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 32 | /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public int findBottomLeftValue(TreeNode root) { Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); TreeNode bl = null; while (!queue.isEmpty()) { int size = queue.size(); bl = queue.peek(); for (int i = 0; i < size; i++) { TreeNode node = queue.poll(); if (node.left != null) { queue.offer(node.left); } if (node.right != null) { queue.offer(node.right); } } } return bl.val; } } |
Solution 2 (DFS):
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 32 33 34 | /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { private int deepest; private int left; public int findBottomLeftValue(TreeNode root) { left = root.val; findBottomLeftValue(root, 0); return left; } private void findBottomLeftValue(TreeNode root, int depth) { if (root == null) { return; } findBottomLeftValue(root.left, depth + 1); findBottomLeftValue(root.right, depth + 1); if (depth > deepest) { deepest = depth; left = root.val; } } } |
Time complexity: O(n).
<3
ReplyDelete