[leetCode]513. 找树左下角的值

题目

链接：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。

递归

1. 确定函数参数及返回值
   由于要遍历所有节点因此返回值void，参数必须要有遍历树的根节点，还需要一个变量来记录最长的深度
2. 确定终止条件
   当遇到叶子节点时就需要统计一下最大的深度
3. 确定单层逻辑

/**
 * 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);
    }
}