2022.2.28 LeetCode —— 二叉树

一、今日刷题

1. 第七部分：二叉树 -- 513. 找树左下角的值2. 第七部分：二叉树 -- 112. 路径总和3. 第七部分：二叉树 -- 113. 路径总和Ⅱ 知识积累

1.递归函数什么时候需要返回值？什么时候不需要返回值？

跳转LeetCode

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

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

答案代码：

一开始做题时不太有思路，其实参考层序遍历很简单：
在层序遍历时，只要把每一层遍历到的第一个节点的值保存下来就可以了。
(突然发现层序遍历能解决很多问题)

package BinaryTree;

import java.util.linkedList;
import java.util.Queue;


public class FindBottomLeftValue {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1, new TreeNode(1, new TreeNode(2), new TreeNode(3)), new TreeNode(6));
        FindBottomLeftValue find = new FindBottomLeftValue();
        int ans = find.findBottomLeftValue(root);
        System.out.println(ans);
    }

    public int findBottomLeftValue(TreeNode root) {
        Queue queue = new linkedList<>();
        int ans = 0;
        if (root == null) {
            return 0; //不写这个if语句也通过了，毕竟假设二叉树中至少有一个节点。
        }

        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 1; i <= size; i++) {
                TreeNode node = queue.poll();
                if (i == 1) {
                    ans = node.val;
                }
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
        }
        return ans;
    }
}

跳转LeetCode

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。

叶子节点 是指没有子节点的节点。

答案代码：

自己的思路，参考 “257.二叉树的所有路径”的代码，将每个路径中节点的和添加到集合中，再遍历集合，与 target 一一比对即可。

package BinaryTree;

import java.util.ArrayList;
import java.util.List;


public class HasPathSum {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1, new TreeNode(1, new TreeNode(2), new TreeNode(3)), new TreeNode(6));
        HasPathSum has = new HasPathSum();
        boolean ans = has.hasPathSum(root, 4);
        System.out.println(ans);
    }

    public boolean hasPathSum(TreeNode root, int targetSum) {
        List list = constructPath(root, 0);
        System.out.println(list);
        for (int n : list) {
            if (n == targetSum) {
                return true;
            }
        }
        return false;
    }

    List list = new ArrayList<>();

    public List constructPath(TreeNode root, int sum){
        if (root != null) {
            sum += root.val;
            if (root.left == null && root.right == null) {
                list.add(sum);
            } else {
                constructPath(root.left, sum);
                constructPath(root.right, sum);
            }
        }
        return list;
    }
}

跳转LeetCode
给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。

叶子节点 是指没有子节点的节点。

如果需要搜索整颗二叉树，那么递归函数就不要返回值，如果要搜索其中一条符合条件的路径，递归函数就需要返回值，因为遇到符合条件的路径了就要及时返回。

可类比今日做题中的前两道，
第一题二叉树左下角的值是多少中，因为要遍历树的所有路径，找出深度最深的叶子节点，所以递归函数不要返回值。
而第二题我们要找一条符合条件的路径，所以递归函数需要返回值，遇到满足条件的路径就要及时返回。