【每日力扣】437. 路径总和 III 与105. 从前序与中序遍历序列构造二叉树

在这里插入图片描述

🔥 个人主页: 黑洞晓威
😀你不必等到非常厉害,才敢开始,你需要开始,才会变的非常厉害

437. 路径总和 III

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

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

解题思路

  1. 由于路径不必从根节点开始,也不必在叶子节点结束,所以对于每个节点,都要尝试以该节点作为路径的起点,向下搜索满足条件的路径数量。
  2. 递归遍历节点,并分别计算包含当前节点以及不包含当前节点的路径数。
  3. 对于每个节点,递归计算包含当前节点的路径数量,然后递归计算不包含当前节点的路径数量。
  4. 统计符合条件的路径数量。

代码实现

class Solution {
    public int pathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return 0;
        }
        
        // 以当前节点为路径起点的路径数 + 以左子树为路径起点的路径数 + 以右子树为路径起点的路径数
        int pathsFromRoot = countPaths(root, targetSum) + pathSum(root.left, targetSum) + pathSum(root.right, targetSum);
        
        return pathsFromRoot;
    }
    
    private int countPaths(TreeNode node, int targetSum) {
        if (node == null) {
            return 0;
        }
        
        int count = 0;
        if (node.val == targetSum) {
            count++;
        }
        
        count += countPaths(node.left, targetSum - node.val);
        count += countPaths(node.right, targetSum - node.val);
        
        return count;
    }
}

105. 从前序与中序遍历序列构造二叉树

给定两个整数数组 preorderinorder ,其中 preorder 是二叉树的先序遍历inorder 是同一棵树的中序遍历,请构造二叉树并返回其根节点。

解题思路

  1. 先序遍历的第一个元素为当前树的根节点。
  2. 在中序遍历中找到根节点的位置,左边为左子树的中序遍历,右边为右子树的中序遍历。
  3. 递归构建左子树和右子树。

代码实现

class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTreeHelper(preorder, inorder, 0, 0, inorder.length - 1);
    }
    
    private TreeNode buildTreeHelper(int[] preorder, int[] inorder, int preStart, int inStart, int inEnd) {
        if (preStart > preorder.length - 1 || inStart > inEnd) {
            return null;
        }
        
        TreeNode root = new TreeNode(preorder[preStart]);
        int inIndex = 0;
        for (int i = inStart; i <= inEnd; i++) {
            if (inorder[i] == root.val) {
                inIndex = i;
            }
        }
        
        root.left = buildTreeHelper(preorder, inorder, preStart + 1, inStart, inIndex - 1);
        root.right = buildTreeHelper(preorder, inorder, preStart + inIndex - inStart + 1, inIndex + 1, inEnd);
        
        return root;
    }
}

最近更新

  1. .Net Core WebAPI参数的传递方式

    2024-05-16 00:14:08       0 阅读
  2. QT--气泡框的实现

    2024-05-16 00:14:08       1 阅读
  3. LeetCode 968.监控二叉树 (hard)

    2024-05-16 00:14:08       0 阅读
  4. leetcode热题100.完全平方数(动态规划进阶)

    2024-05-16 00:14:08       0 阅读
  5. leetcode328-Odd Even Linked List

    2024-05-16 00:14:08       0 阅读
  6. C 语言设计模式(结构型)

    2024-05-16 00:14:08       0 阅读
  7. v-if 与 v-show(vue3条件渲染)

    2024-05-16 00:14:08       0 阅读
  8. kafka防止消息丢失配置

    2024-05-16 00:14:08       0 阅读

热门阅读

  1. 大前端之Flex 布局

    2024-05-16 00:14:08       2 阅读
  2. Linux-笔记 man手册命令

    2024-05-16 00:14:08       2 阅读
  3. linq常用方法

    2024-05-16 00:14:08       2 阅读
  4. FAT32 文件系统详解

    2024-05-16 00:14:08       2 阅读
  5. 3099.哈沙德数——力扣

    2024-05-16 00:14:08       2 阅读
  6. Unity Mirror 从入门到入神(二)

    2024-05-16 00:14:08       2 阅读
  7. nmap端口扫描工具——LInux

    2024-05-16 00:14:08       4 阅读
  8. C中Mysql的基本api接口

    2024-05-16 00:14:08       2 阅读