寻找左下角的值leetcode题解513-前序遍历递归法

声明：问题描述来源leetcode
实际上和leetcode102的层序遍历是一样的题目

一、问题描述：

513. 找树左下角的值

难度中等399

给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。

假设二叉树中至少有一个节点。

示例 1:

输入: root = [2,1,3]
输出: 1
1
2

示例 2:

输入: [1,2,3,4,null,5,6,null,null,7]
输出: 7
1
2

提示:

• 二叉树的节点个数的范围是 [1,104]
• -231 <= Node.val <= 231 - 1

二、题解：

思路1

前序遍历,讲每一层数据放入一个子链表里，从左到右依次排列

class Solution {
    List<List<Integer>> lists = new LinkedList<>();
    public int findBottomLeftValue(TreeNode root) {
        lists.add(new LinkedList<>());
        searchGoalByOrder(0,root);
        return lists.get(lists.size() - 1).get(0);
    }

    private void searchGoalByOrder(int order, TreeNode root) {
        lists.get(order).add(root.val);
        if (root.left != null){
            if (order + 1 > lists.size() - 1) lists.add(new LinkedList<>());
            searchGoalByOrder(order + 1,root.left);
        }
        
        if (root.right != null){
            if (order + 1 > lists.size() - 1) lists.add(new LinkedList<>());
            searchGoalByOrder(order + 1,root.right);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

思路2

分析上面的，因为一个子链表只需要看最左边的元素，因此，当一个链表添加了第一个树节点的val值，就拒绝该层的其他树节点的val值即可，省去不必要的插入的操作，降低空间复杂度和时间复杂的。

优化

class Solution {
    List<Integer> list = new LinkedList<>();

    public int findBottomLeftValue(TreeNode root) {
        searchGoalByOrder(0,root);
        return list.get(list.size() - 1);
    }

    private void searchGoalByOrder(int order, TreeNode root) {
        if (list.size() <= order) list.add(root.val);
        if (root.left != null) searchGoalByOrder(order + 1, root.left);
        if (root.right != null) searchGoalByOrder(order + 1, root.right);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

end