题目
链接:https://leetcode-cn.com/problems/find-bottom-left-tree-value
给定一个二叉树,在树的最后一行找到最左边的值。
示例 1:
输入:
2
/ \
1 3
输出:
1
示例 2:
输入:
1
/ \
2 3
/ / \
4 5 6
/
7
输出:
7
注意: 您可以假设树(即给定的根节点)不为 NULL。
递归
- 确定函数参数及返回值
由于要遍历所有节点因此返回值void,参数必须要有遍历树的根节点,还需要一个变量来记录最长的深度 - 确定终止条件
当遇到叶子节点时就需要统计一下最大的深度 - 确定单层逻辑
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
int maxDepth = Integer.MIN_VALUE;
int maxLeftValue;
public int findBottomLeftValue(TreeNode root) {
traversal(root, 0);
return maxLeftValue;
}
private void traversal(TreeNode cur, int depth) {
if (cur.left == null && cur.right == null) {
if (depth > maxDepth) {
maxDepth = depth;
maxLeftValue = cur.val;
}
}
if (cur.left != null)
traversal(cur.left, depth + 1);
if (cur.right != null)
traversal(cur.right, depth + 1);
}
}