描述
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.
分析
其实就是求树的高度,深度优先遍历即可。
解决方案1(Java)
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
|
class Solution { private int value = 0; private int maxDepth = 0; public int findBottomLeftValue(TreeNode root) { dfs(root, 1); return value; } private void dfs(TreeNode root, int depth) { if (depth > maxDepth) { value = root.val; maxDepth = depth; } if (root.left != null) { dfs(root.left, depth + 1); } if (root.right != null) { dfs(root.right, depth + 1); } } }
|