当前位置：个人在线分享 > 【LeetCode 随笔】面试经典 150 题【中等＋困难】持续更新中。。。

【LeetCode 随笔】面试经典 150 题【中等＋困难】持续更新中。。。

作者 : admin 本文共6143个字，预计阅读时间需要16分钟发布时间： 2024-06-10 共3人阅读

【LeetCode 随笔】面试经典 150 题【中等＋困难】持续更新中。。。插图

文章目录

- 117.【中等】填充每个节点的下一个右侧节点指针 II
- 114.【中等】二叉树展开为链表
- 129.【中等】求根节点到叶节点数字之和
- 124.【困难】二叉树中的最大路径和
- 173.【中等】二叉搜索树迭代器

🌈你好呀！我是山顶风景独好
🎈欢迎踏入我的博客世界，能与您在此邂逅，真是缘分使然！😊
🌸愿您在此停留的每一刻，都沐浴在轻松愉悦的氛围中。
📖这里不仅有丰富的知识和趣味横生的内容等您来探索，更是一个自由交流的平台，期待您留下独特的思考与见解。🌟
🚀让我们一起踏上这段探索与成长的旅程，携手挖掘更多可能，共同进步！💪✨

117.【中等】填充每个节点的下一个右侧节点指针 II

给定一个二叉树：

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL 。
初始状态下，所有 next 指针都被设置为 NULL 。

示例 1：

输入：root = [1,2,3,4,5,null,7]
输出：[1,#,2,3,#,4,5,7,#]
解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。序列化输出按层序遍历顺序（由 next 指针连接），‘#’ 表示每层的末尾。
示例 2：
输入：root = []
输出：[]

class Solution {  
    // 连接二叉树的每一层  
    public Node connect(Node root) {  
        // 如果根节点为空，则直接返回null  
        if (root == null) {  
            return null;  
        }  
  
        // 创建一个队列用于层序遍历  
        Queue<Node> queue = new ArrayDeque<Node>();  
        // 将根节点加入队列  
        queue.offer(root);  
  
        // 当队列不为空时，说明还有节点需要处理  
        while (!queue.isEmpty()) {  
            // 获取当前层的节点数量  
            int n = queue.size();  
            // 初始化last为null，用于记录当前层的上一个节点  
            Node last = null;  
  
            // 遍历当前层的所有节点  
            for (int i = 1; i <= n; ++i) {  
                // 出队一个节点  
                Node f = queue.poll();  
  
                // 如果该节点的左子节点不为空，将其加入队列  
                if (f.left != null) {  
                    queue.offer(f.left);  
                }  
  
                // 如果该节点的右子节点不为空，将其加入队列  
                if (f.right != null) {  
                    queue.offer(f.right);  
                }  
  
                // 如果这不是当前层的第一个节点（即i != 1），则将上一个节点last的next指向当前节点f  
                if (i != 1) {  
                    last.next = f;  
                }  
  
                // 更新last为当前节点f，以便处理下一个节点  
                last = f;  
            }  
        }  
  
        // 返回根节点，此时整棵树的每一层节点都已经连接好了  
        return root;  
    }  
}

114.【中等】二叉树展开为链表

给你二叉树的根结点 root ，请你将它展开为一个单链表：
展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
展开后的单链表应该与二叉树先序遍历顺序相同。

示例 1：

输入：root = [1,2,5,3,4,null,6]
输出：[1,null,2,null,3,null,4,null,5,null,6]
示例 2：
输入：root = []
输出：[]
示例 3：
输入：root = [0]
输出：[0]

class Solution {  
    // 平展二叉树的方法，将二叉树转换为右子树链表的形式  
    public void flatten(TreeNode root) {  
        // 创建一个列表，用于存储前序遍历的结果  
        List<TreeNode> list = new ArrayList<TreeNode>();  
        // 对二叉树进行前序遍历，并将节点添加到列表中  
        preorderTraversal(root, list);  
  
        // 获取列表中节点的数量  
        int size = list.size();  
  
        // 从第二个节点开始遍历列表（索引从1开始，因为第一个节点已经是root了）  
        for (int i = 1; i < size; i++) {  
            // 获取前一个节点和当前节点  
            TreeNode prev = list.get(i - 1), curr = list.get(i);  
  
            // 将前一个节点的左子树设置为null（因为我们要平展树）  
            prev.left = null;  
            // 将前一个节点的右子树设置为当前节点，从而实现平展效果  
            prev.right = curr;  
        }  
    }  
  
    // 前序遍历二叉树的方法，将遍历到的节点添加到给定的列表中  
    public void preorderTraversal(TreeNode root, List<TreeNode> list) {  
        // 如果当前节点不为null，则进行以下操作  
        if (root != null) {  
            // 将当前节点添加到列表中  
            list.add(root);  
            // 递归遍历左子树  
            preorderTraversal(root.left, list);  
            // 递归遍历右子树  
            preorderTraversal(root.right, list);  
        }  
    }  
}

129.【中等】求根节点到叶节点数字之和

给你一个二叉树的根节点 root ，树中每个节点都存放有一个 0 到 9 之间的数字。
每条从根节点到叶节点的路径都代表一个数字：
例如，从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123 。
计算从根节点到叶节点生成的所有数字之和。
叶节点是指没有子节点的节点。

示例 1：

输入：root = [1,2,3]
输出：25
解释：
从根到叶子节点路径 1->2 代表数字 12
从根到叶子节点路径 1->3 代表数字 13
因此，数字总和 = 12 + 13 = 25
示例 2：

输入：root = [4,9,0,5,1]
输出：1026
解释：
从根到叶子节点路径 4->9->5 代表数字 495
从根到叶子节点路径 4->9->1 代表数字 491
从根到叶子节点路径 4->0 代表数字 40
因此，数字总和 = 495 + 491 + 40 = 1026

class Solution {  
    // 主方法，接收一个树的根节点，并返回所有从根到叶子节点的数字之和  
    public int sumNumbers(TreeNode root) {  
        return dfs(root, 0); // 调用深度优先搜索方法，初始和为0  
    }  
  
    // 深度优先搜索方法，递归地遍历树的每个节点  
    public int dfs(TreeNode root, int prevSum) {  
        if (root == null) { // 如果节点为空，则返回0  
            return 0;  
        }  
        // 计算当前路径上的数字之和，将前一个节点值的10倍加上当前节点的值  
        int sum = prevSum * 10 + root.val;   
          
        if (root.left == null && root.right == null) { // 如果当前节点是叶子节点  
            return sum; // 返回当前路径的数字之和  
        } else {  
            // 如果不是叶子节点，则递归地对左子树和右子树进行深度优先搜索，  
            // 并将两个子树的结果相加  
            return dfs(root.left, sum) + dfs(root.right, sum);   
        }  
    }  
}

124.【困难】二叉树中的最大路径和

二叉树中的路径被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中至多出现一次。该路径至少包含一个节点，且不一定经过根节点。
路径和是路径中各节点值的总和。
给你一个二叉树的根节点 root ，返回其最大路径和。

示例 1：

输入：root = [1,2,3]
输出：6
解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6
示例 2：

输入：root = [-10,9,20,null,null,15,7]
输出：42
解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
private int max = Integer.MIN_VALUE; // 初始化最大路径和为整数的最小值  
  
public int maxPathSum(TreeNode root) {  
    // 调用递归函数计算包含根节点的最大路径和  
    containCurNodeMaxSum(root);  
    // 返回找到的最大路径和  
    return max;  
}  
  
private int containCurNodeMaxSum(TreeNode node) {  
    if (node == null) {  
        // 如果节点为空，返回0表示没有路径和  
        return 0;  
    }  
    // 递归计算左子树中包含左孩子节点的最大路径和  
    int leftMax = containCurNodeMaxSum(node.left);  
    // 递归计算右子树中包含右孩子节点的最大路径和  
    int rightMax = containCurNodeMaxSum(node.right);  
      
    // 计算当前节点为根节点的三种可能路径和的最大值：  
    // 1. 只包含当前节点值  
    // 2. 包含当前节点值和左子树中的最大路径和  
    // 3. 包含当前节点值和右子树中的最大路径和  
    int curMax = Math.max(Math.max(node.val + leftMax, node.val + rightMax), node.val);  
      
    // 更新全局最大路径和：  
    // 1. 可能是当前节点值加上左子树和右子树中的最大路径和（当左右子树都贡献正值时）  
    // 2. 可能是以当前节点为根的其他路径和（即curMax）  
    // 3. 可能是之前已经计算过的全局最大路径和  
    max = Math.max(Math.max(node.val + leftMax + rightMax, curMax), max);  
      
    // 返回以当前节点为根的最大路径和（注意：这里只返回了当前节点为根节点的三种可能路径和的最大值，  
    // 并没有包含左右子树同时贡献正值的情况，因为这种情况已经在更新全局最大路径和时考虑了）  
    return curMax;  
}
}

173.【中等】二叉搜索树迭代器

实现一个二叉搜索树迭代器类BSTIterator ，表示一个按中序遍历二叉搜索树（BST）的迭代器：
BSTIterator(TreeNode root) 初始化 BSTIterator 类的一个对象。BST 的根节点 root 会作为构造函数的一部分给出。指针应初始化为一个不存在于 BST 中的数字，且该数字小于 BST 中的任何元素。
boolean hasNext() 如果向指针右侧遍历存在数字，则返回 true ；否则返回 false 。
int next()将指针向右移动，然后返回指针处的数字。
注意，指针初始化为一个不存在于 BST 中的数字，所以对 next() 的首次调用将返回 BST 中的最小元素。
你可以假设 next() 调用总是有效的，也就是说，当调用 next() 时，BST 的中序遍历中至少存在一个下一个数字。

示例：

输入
[“BSTIterator”, “next”, “next”, “hasNext”, “next”, “hasNext”, “next”, “hasNext”, “next”, “hasNext”]
[[[7, 3, 15, null, null, 9, 20]], [], [], [], [], [], [], [], [], []]
输出
[null, 3, 7, true, 9, true, 15, true, 20, false]
解释
BSTIterator bSTIterator = new BSTIterator([7, 3, 15, null, null, 9, 20]);
bSTIterator.next(); // 返回 3
bSTIterator.next(); // 返回 7
bSTIterator.hasNext(); // 返回 True
bSTIterator.next(); // 返回 9
bSTIterator.hasNext(); // 返回 True
bSTIterator.next(); // 返回 15
bSTIterator.hasNext(); // 返回 True
bSTIterator.next(); // 返回 20
bSTIterator.hasNext(); // 返回 False

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
// 定义一个BSTIterator类，用于迭代二叉搜索树（BST）  
class BSTIterator {  
    // 定义一个索引变量，用于追踪当前迭代到的元素位置  
    private int idx;  
    // 定义一个列表，用于存储二叉搜索树的中序遍历结果  
    private List<Integer> arr;  
  
    // 构造函数，接收一个二叉搜索树的根节点作为参数  
    public BSTIterator(TreeNode root) {  
        // 初始化索引为0  
        idx = 0;  
        // 初始化存储列表  
        arr = new ArrayList<Integer>();  
        // 调用中序遍历方法，将遍历结果存入列表  
        inorderTraversal(root, arr);  
    }  
  
    // 返回下一个最小的元素，并将索引加1  
    public int next() {  
        return arr.get(idx++);  
    }  
  
    // 判断是否还有下一个元素可供迭代  
    public boolean hasNext() {  
        return idx < arr.size();  
    }  
  
    // 定义一个私有方法，用于执行二叉搜索树的中序遍历  
    private void inorderTraversal(TreeNode root, List<Integer> arr) {  
        // 如果当前节点为空，则直接返回  
        if (root == null) {  
            return;  
        }  
        // 先递归遍历左子树  
        inorderTraversal(root.left, arr);  
        // 将当前节点的值添加到列表中  
        arr.add(root.val);  
        // 再递归遍历右子树  
        inorderTraversal(root.right, arr);  
    }  
}
/**
 * Your BSTIterator object will be instantiated and called as such:
 * BSTIterator obj = new BSTIterator(root);
 * int param_1 = obj.next();
 * boolean param_2 = obj.hasNext();
 */

✨ 这就是今天要分享给大家的全部内容了，我们下期再见！😊
🏠 我在CSDN等你哦！我的主页😍

Java leetcode 二叉树后端数据结构算法

本站无任何商业行为
个人在线分享 » 【LeetCode 随笔】面试经典 150 题【中等＋困难】持续更新中。。。

admin 钻石

分享到：

E-->