原题链接&&讲解
222. 完全二叉树的节点个数
112. 路径总和
106.从中序与后序遍历序列构造二叉树
讲解>>代码随想录
222. 完全二叉树的节点个数
题目
给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。
完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层（从第 0 层开始），则该层包含 1~ 2h 个节点。
思路
法一：采用递归
法二：迭代
代码
java">// 递归
class Solution {public int countNodes(TreeNode root) {if(root == null) {return 0;}return countNodes(root.left) + countNodes(root.right) + 1;}
}
java">class Solution {// 迭代法深度优先搜索public int countNodes(TreeNode root) {if (root == null) {return 0;}Stack<TreeNode> stack = new Stack<>();stack.push(root);int result = 0;while (!stack.isEmpty()) {TreeNode node = stack.pop();result++; // 计数当前节点// 如果有右子节点，压入栈中if (node.right != null) {stack.push(node.right);}// 如果有左子节点，压入栈中if (node.left != null) {stack.push(node.left);}}return result;}
}
java">class Solution {// 迭代法深度优先搜索public int countNodes(TreeNode root) {if (root == null) {return 0;}Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);int result = 0;while (!queue.isEmpty()) {int size = queue.size();while (size-- > 0) {TreeNode cur = queue.poll();result++;if (cur.left != null) queue.offer(cur.left);if (cur.right != null) queue.offer(cur.right);}}return result;}
}
112. 路径总和
题目
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。
叶子节点 是指没有子节点的节点。
思路
DFS思路:
从根节点开始，沿着每一条路径向下遍历，直到找到一条路径满足所有节点值之和等于 targetSum 或者遍历完所有可能的路径。
BFS思路:拿层先来做显然不是很合适, 不过也可以去实现, 要多加一个队列来方便计算和
代码
java">class Solution {public boolean hasPathSum(TreeNode root, int targetSum) {// 如果当前节点为空,返回falseif(root==null){return false;}// 否则,减去当前节点值targetSum -= root.val;// 检查是否为叶子节点并且路径和等于目标和if (root.left == null && root.right == null) {return targetSum == 0;}// 递归左右子树return hasPathSum(root.left, targetSum) || hasPathSum(root.right, targetSum);}
}
java">class Solution {public boolean hasPathSum(TreeNode root, int targetSum) {if (root == null) {return false;}// 使用队列存储节点及其对应的路径和Queue<TreeNode> nodeQueue = new LinkedList<>();Queue<Integer> sumQueue = new LinkedList<>();nodeQueue.offer(root);sumQueue.offer(root.val);while (!nodeQueue.isEmpty()) {TreeNode currentNode = nodeQueue.poll();int currentSum = sumQueue.poll();// 检查是否为叶子节点并且路径和等于目标和if (currentNode.left == null && currentNode.right == null && currentSum == targetSum) {return true;}// 将左子节点及更新后的路径和加入队列if (currentNode.left != null) {nodeQueue.offer(currentNode.left);sumQueue.offer(currentSum + currentNode.left.val);}// 将右子节点及更新后的路径和加入队列if (currentNode.right != null) {nodeQueue.offer(currentNode.right);sumQueue.offer(currentSum + currentNode.right.val);}}return false;}
}
106.从中序与后序遍历序列构造二叉树
题目
给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。
思路
首先需要理解中序和后序遍历的含义, 这是必要的.
我们可以
通过后序遍历的结果来确定根节点, 但是后序遍历无法确定根节点的左右子树
那么我们可以通过中序遍历来确定根节点的左右子树, 根节点已经在后序遍历中找到了.
就这样通过中序和后序遍历的配合, 我们可以逐个判断节点的位置, 将二叉树画出来.
那么接下来就是代码实现
步骤
- 确定根节点：
后序遍历的最后一个元素是树的根节点。- 分割左右子树：
在中序遍历中找到根节点的位置，它左边的所有节点属于左子树，右边的所有节点属于右子树。- 递归构造子树：
根据中序遍历中根节点的位置，可以确定左右子树各自的中序和后序遍历序列。
对于每个子树，重复步骤1和2的过程，即从后序遍历中找到子树的根节点，并在中序遍历中划分出更小的左右子树。- 终止条件：
当没有更多的节点用于构建子树时（即后序遍历或中序遍历为空），返回 null 表示当前递归分支结束。
代码
java">class Solution {private int postIndex;private HashMap<Integer, Integer> indexMap = new HashMap<>();public TreeNode buildTree(int[] inorder, int[] postorder) {if (inorder == null || postorder == null || inorder.length != postorder.length) {return null;}postIndex = postorder.length - 1;// 构建索引映射以获取中序序列中值到索引的快速查找int idx = 0;for (Integer val : inorder) {indexMap.put(val, idx++);}return buildTreeHelper(inorder, postorder, 0, inorder.length - 1);}private TreeNode buildTreeHelper(int[] inorder, int[] postorder, int inLeft, int inRight) {// 如果没有元素构造子树了，则返回nullif (inLeft > inRight) {return null;}// 选择 postIndex 位置元素作为当前子树根节点int rootValue = postorder[postIndex];TreeNode root = new TreeNode(rootValue);postIndex--;// 根据root所在中序的位置划分左右子树int index = indexMap.get(rootValue);// 先构造右子树，再构造左子树（因为后序遍历是“左->右->根”，所以从后往前）root.right = buildTreeHelper(inorder, postorder, index + 1, inRight);root.left = buildTreeHelper(inorder, postorder, inLeft, index - 1);return root;}
}
