437. 路径总和 III-蒲公英云

437. 路径总和 III

电玩女神 2023-10-11 18:19 157阅读 0赞

打卡!!!每日一题

今天给大家带来一道深度优先遍历的题目，要知道树的前序遍历就是深度优先遍历，按照这个思路很多题目就会很轻松的解决。

题目描述：437. 路径总和 III

给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的路径的数目。

路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

题目示例：
在这里插入图片描述

在这里插入图片描述

这道题我只需要穷举就好，思路也很简单，我们只需记住每一个结点的父节点，然后一直向上去找，一直找到根节点为止。

1.保存每一个结点的父节点

/**

 * 子--->父
 */
static Map<TreeNode, TreeNode> map = new HashMap<>();
public static void dfs(TreeNode root) {
    if (root == null) {
        return;
    }
    if (root.left != null) {
        map.put(root.left, root);
    }
    if (root.right != null) {
        map.put(root.right, root);
    }
    dfs(root.left);
    dfs(root.right);
}

2.向上穷举

while (map.get(t) != null) {

            t = map.get(t);
            ans += t.val;
            if (ans == targetSum) {
                count++;
                break;
            }
        }

最终代码如下：

public class 路径总和III_437 {
    /**
     * 子--->父
     */
    static Map<TreeNode, TreeNode> map = new HashMap<>();
    public static int pathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return 0;
        }
        dfs(root);
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        int count = 0;
        while (!queue.isEmpty()) {
            TreeNode t = queue.peek();
            long ans = t.val;
            if (ans == targetSum) count++;
            while (map.get(t) != null) {
                t = map.get(t);
                ans += t.val;
                if (ans == targetSum) {
                    count++;
                    break;
                }
            }
            t = queue.poll();
            if (t.left != null) {
                queue.add(t.left);
            }
            if (t.right != null) {
                queue.add(t.right);
            }
        }
        return count;
    }
    public static void dfs(TreeNode root) {
        if (root == null) {
            return;
        }
        if (root.left != null) {
            map.put(root.left, root);
        }
        if (root.right != null) {
            map.put(root.right, root);
        }
        dfs(root.left);
        dfs(root.right);
    }
}