437. 路径总和 III

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

打卡!!!每日一题

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

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

> 给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。
> 
> 路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

题目示例：  
![在这里插入图片描述][293c14fe077948059e5cfe7b38a24c1f.jpeg_pic_center]

![在这里插入图片描述][3bede9f0a11549b99c2600653715e746.png_pic_center]

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

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

我刚开始写的时候ans写的是int类型的，结果一直无法通过最后一个测试用例  
![在这里插入图片描述][4e1129fe563547309989054c2ca9faaf.png_pic_center]

后来我才注意到，虽然树的每一个结点的都是int类型，但是整型超过128之后就无法通过==来进行对比，所以声明为 long或者更高精度的值都可以。

[437. _ III]: https://leetcode.cn/problems/path-sum-iii/
[293c14fe077948059e5cfe7b38a24c1f.jpeg_pic_center]: https://img-blog.csdnimg.cn/293c14fe077948059e5cfe7b38a24c1f.jpeg#pic_center
[3bede9f0a11549b99c2600653715e746.png_pic_center]: https://img-blog.csdnimg.cn/3bede9f0a11549b99c2600653715e746.png#pic_center
[4e1129fe563547309989054c2ca9faaf.png_pic_center]: https://img-blog.csdnimg.cn/4e1129fe563547309989054c2ca9faaf.png#pic_center