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

本文主要是介绍【每日力扣】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. 从前序与中序遍历序列构造二叉树

给定两个整数数组 preorder 和 inorder ，其中 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;}
}

这篇关于【每日力扣】437. 路径总和 III 与105. 从前序与中序遍历序列构造二叉树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---