代码随想录算法日记day16 | 513.找树左下角的值、112. 路径总和、106.从中序与后序遍历序列构造二叉树

原题链接&&讲解

222. 完全二叉树的节点个数
112. 路径总和
106.从中序与后序遍历序列构造二叉树
讲解>>代码随想录

222. 完全二叉树的节点个数

题目

给你一棵完全二叉树的根节点 root ，求出该树的节点个数。

完全二叉树的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层（从第 0 层开始），则该层包含 1~ 2h 个节点。

思路

法一：采用递归
法二：迭代

代码

// 递归
class Solution {
    public int countNodes(TreeNode root) {
        if(root == null) {
            return 0;
        }
        return countNodes(root.left) + countNodes(root.right) + 1;
    }
}

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

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思路:拿层先来做显然不是很合适, 不过也可以去实现, 要多加一个队列来方便计算和

代码

class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        // 如果当前节点为空,返回false
        if(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);
    }
}

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 表示当前递归分支结束。

代码

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) {
        // 如果没有元素构造子树了，则返回null
        if (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;
    }
}