代码随想录算法训练营第十八天 | 找树左下角的值、路经总和、构造二叉树

27次阅读
没有评论

513. 找树左下角的值

leetcode
文档题解
视频题解

注意:左下角的意思是最后一层最左边的节点,不一定是左孩子。

递归法。因为要找深度最深的节点,所以要记录节点的深度

class Solution {
    // 最大深度
    private int maxDepth = Integer.MIN_VALUE;
    // 结果
    private int result;

    public int findBottomLeftValue(TreeNode root) {helper(root, 1);
        return result;
    }

    public void helper(TreeNode node, int depth) {
        // 叶子节点
        // 这里的处理无关遍历顺序,因为是在找最深的叶子节点
        if (node.left == null && node.right == null) {
            // 找深度最深的节点(即最后一层)// 因为是前中后序遍历,左节点的遍历一定在右节点之前
            // 所以即便最后一层有左右两个子节点,也一定是左节点执行这个判断,更新 maxDepth、result
            // 右节点排不上号,这就保证了找到最后一层最靠左的节点
            if (depth > maxDepth) {
                maxDepth = depth;
                result = node.val;
            }
        }

        if (node.left != null) {
            depth++;
            helper(node.left, depth);
            depth--;
        }

        if (node.right != null) {
            depth++;
            helper(node.right, depth);
            depth--;
        }
    }
}

112. 路经总和

leetcode
文档题解
视频题解

本题的本质是进行深度优先搜索,找到满足条件的路径。使用减法做匹配,每次深入时都减去当前节点的值,直到查找到叶子节点,看查找值和叶子节点是否相等。

// 递归法
class Solution {public boolean hasPathSum(TreeNode root, int targetSum) {if (root == null) return false;

        // 到达叶子节点,如果叶子节点的值正好是要找的值,则表示找到答案
        if (root.left == null && root.right == null) return root.val == targetSum;

        if (root.left != null) {
            // 隐藏着回溯
            if (hasPathSum(root.left, targetSum - root.val)) return true;
        }

        if (root.right != null) {if (hasPathSum(root.right, targetSum - root.val)) return true;
        }

        return false;
    }
}
// 迭代法
class Solution {public boolean hasPathSum(TreeNode root, int targetSum) {if (root == null) return false;

        // 使用栈模拟递归,值为节点和目标值的 pair
        Stack<Pair<TreeNode, Integer>> stack = new Stack<>();
        stack.push(new Pair<>(root, targetSum));

        while (!stack.isEmpty()) {Pair<TreeNode, Integer> p = stack.pop();
            TreeNode node = p.getKey();
            int sum = p.getValue();

            // 重点,只有是叶子节点,且 node.val == 目标值的才是结果,然后直接返回
            if (node.left == null && node.right == null && node.val == sum) return true;

            if (node.right != null) {stack.push(new Pair<>(node.right, sum - node.val));
            }

            if (node.left != null) {stack.push(new Pair<>(node.left, sum - node.val));
            }
        }

        return false;
    }
}

113. 路径总和 II

leetcode
文档题解
视频题解

因为要记录所有符合的路径,所以需要存储结果,并且每次深入时需要记录访问过的路径。

class Solution {public List<List<Integer>> pathSum(TreeNode root, int targetSum) {List<List<Integer>> res = new LinkedList<>();
        if (root != null) {traversal(root, new LinkedList<>(), targetSum, res);
        }
        return res;
    }

    public void traversal(TreeNode node, Deque<Integer> path, int target, List<List<Integer>> res) {
        // 访问当前节点,放入 path
        path.offerLast(node.val);
        // 到达路径终点,即叶子节点,产生解的地方
        if (node.left == null && node.right == null && node.val == target) {res.add((List<Integer>) new LinkedList<>(path));
            // res.add((List<Integer>) path);
        }
        if (node.left != null) {
            // target 的深入与回溯
            traversal(node.left, path, target - node.val, res);
        }
        if (node.right != null) {traversal(node.right, path, target - node.val, res);
        }
        // 访问结束,退出 path(回溯)path.pollLast();}
}

106. 从中序与后序遍历序列构造二叉树

leetcode
文档题解
视频题解

先根据后序遍历找到 root,然后根据 root 去中序遍历中划分左右子树的中序遍历,根据左子树中序序列的长度(左子树的中后序长度是相同的),也能去后序遍历中划分左右子树的后序遍历,然后分治,递归处理。

class Solution {public TreeNode buildTree(int[] inorder, int[] postorder) {if (inorder.length == 0 || postorder.length == 0) return null;
        TreeNode root = new TreeNode(postorder[postorder.length - 1]);
        if (postorder.length == 1) return root;

        int idx = -1;
        for (int i = 0; i < inorder.length; i++) {if (postorder[postorder.length - 1] == inorder[i]) {
                idx = i;
                break;
            }
        }

        // 分割左右子树的中序和后续数组
        int[] leftInorder = Arrays.copyOfRange(inorder, 0, idx);
        int[] leftPostorder = Arrays.copyOfRange(postorder, 0, leftInorder.length);
        int[] rightInorder = Arrays.copyOfRange(inorder, idx + 1, inorder.length);
        int[] rightPostorder = Arrays.copyOfRange(postorder, leftPostorder.length, postorder.length - 1);

        root.left = buildTree(leftInorder, leftPostorder);
        root.right = buildTree(rightInorder, rightPostorder);

        return root;
    }
}

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

leetcode
文档题解

class Solution {public TreeNode buildTree(int[] preorder, int[] inorder) {if (preorder.length == 0 || inorder.length == 0) return null;
        TreeNode root = new TreeNode(preorder[0]);
        if (preorder.length == 1) return root;

        int idx = -1;
        for (int i = 0; i < inorder.length; i++) {if (preorder[0] == inorder[i]) {
                idx = i;
                break;
            }
        }

        int[] leftInorder = Arrays.copyOfRange(inorder, 0, idx);
        int[] leftPreorder = Arrays.copyOfRange(preorder, 1, leftInorder.length + 1);
        int[] rightInorder = Arrays.copyOfRange(inorder, idx + 1, inorder.length);
        int[] rightPreorder = Arrays.copyOfRange(preorder, leftPreorder.length + 1, preorder.length);

        root.left = buildTree(leftPreorder, leftInorder);
        root.right = buildTree(rightPreorder, rightInorder);

        return root;
    }
}
正文完
 0
狐耳阿霖
版权声明:本站原创文章,由 狐耳阿霖 于2024-02-22发表,共计3923字。
转载说明:除特殊说明外本站文章皆由CC-4.0协议发布,转载请注明出处。
评论(没有评论)