备案控制台
开发者社区 人工智能 文章 正文

class036 二叉树高频题目-上-不含树型dp【算法】

2023-12-21 33
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： class036 二叉树高频题目-上-不含树型dp【算法】

class036 二叉树高频题目-上-不含树型dp

code1 102. 二叉树的层序遍历

// 二叉树的层序遍历

// 测试链接 : https://leetcode.cn/problems/binary-tree-level-order-traversal/

code1 普通bfs

code2 一次操作一层

package class036;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
// 二叉树的层序遍历
// 测试链接 : https://leetcode.cn/problems/binary-tree-level-order-traversal/
public class Code01_LevelOrderTraversal {
  // 不提交这个类
  public static class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
  }
  // 提交时把方法名改为levelOrder，此方法为普通bfs，此题不推荐
  public static List<List<Integer>> levelOrder1(TreeNode root) {
    List<List<Integer>> ans = new ArrayList<>();
    if (root != null) {
      Queue<TreeNode> queue = new LinkedList<>();
      HashMap<TreeNode, Integer> levels = new HashMap<>();
      queue.add(root);
      levels.put(root, 0);
      while (!queue.isEmpty()) {
        TreeNode cur = queue.poll();
        int level = levels.get(cur);
        if (ans.size() == level) {
          ans.add(new ArrayList<>());
        }
        ans.get(level).add(cur.val);
        if (cur.left != null) {
          queue.add(cur.left);
          levels.put(cur.left, level + 1);
        }
        if (cur.right != null) {
          queue.add(cur.right);
          levels.put(cur.right, level + 1);
        }
      }
    }
    return ans;
  }
  // 如果测试数据量变大了就修改这个值
  public static int MAXN = 2001;
  public static TreeNode[] queue = new TreeNode[MAXN];
  public static int l, r;
  // 提交时把方法名改为levelOrder，此方法为每次处理一层的优化bfs，此题推荐
  public static List<List<Integer>> levelOrder2(TreeNode root) {
    List<List<Integer>> ans = new ArrayList<>();
    if (root != null) {
      l = r = 0;
      queue[r++] = root;
      while (l < r) { // 队列里还有东西
        int size = r - l;
        ArrayList<Integer> list = new ArrayList<Integer>();
        for (int i = 0; i < size; i++) {
          TreeNode cur = queue[l++];
          list.add(cur.val);
          if (cur.left != null) {
            queue[r++] = cur.left;
          }
          if (cur.right != null) {
            queue[r++] = cur.right;
          }
        }
        ans.add(list);
      }
    }
    return ans;
  }
}

code2 103. 二叉树的锯齿形层序遍历

// 二叉树的锯齿形层序遍历

// 测试链接 : https://leetcode.cn/problems/binary-tree-zigzag-level-order-traversal/

code 遍历

package class036;
import java.util.ArrayList;
import java.util.List;
// 二叉树的锯齿形层序遍历
// 测试链接 : https://leetcode.cn/problems/binary-tree-zigzag-level-order-traversal/
public class Code02_ZigzagLevelOrderTraversal {
  // 不提交这个类
  public static class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
  }
  // 提交以下的方法
  // 用每次处理一层的优化bfs就非常容易实现
  // 如果测试数据量变大了就修改这个值
  public static int MAXN = 2001;
  public static TreeNode[] queue = new TreeNode[MAXN];
  public static int l, r;
  public static List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    List<List<Integer>> ans = new ArrayList<>();
    if (root != null) {
      l = r = 0;
      queue[r++] = root;
      // false 代表从左往右
      // true 代表从右往左
      boolean reverse = false; 
      while (l < r) {
        int size = r - l;
        ArrayList<Integer> list = new ArrayList<Integer>();
        // reverse == false, 左 -> 右， l....r-1, 收集size个
        // reverse == true,  右 -> 左， r-1....l, 收集size个
        // 左 -> 右, i = i + 1
        // 右 -> 左, i = i - 1
        for (int i = reverse ? r - 1 : l, j = reverse ? -1 : 1, k = 0; k < size; i += j, k++) {
          TreeNode cur = queue[i];
          list.add(cur.val);
        }
        for (int i = 0; i < size; i++) {
          TreeNode cur = queue[l++];
          if (cur.left != null) {
            queue[r++] = cur.left;
          }
          if (cur.right != null) {
            queue[r++] = cur.right;
          }
        }
        ans.add(list);
        reverse = !reverse;
      }
    }
    return ans;
  }
}

code3 662. 二叉树最大宽度

// 二叉树的最大特殊宽度

// 测试链接 : https://leetcode.cn/problems/maximum-width-of-binary-tree/

package class036;
// 二叉树的最大特殊宽度
// 测试链接 : https://leetcode.cn/problems/maximum-width-of-binary-tree/
public class Code03_WidthOfBinaryTree {
  // 不提交这个类
  public static class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
  }
  // 提交以下的方法
  // 用每次处理一层的优化bfs就非常容易实现
  // 如果测试数据量变大了就修改这个值
  public static int MAXN = 3001;
  public static TreeNode[] nq = new TreeNode[MAXN];
  public static int[] iq = new int[MAXN];
  public static int l, r;
  public static int widthOfBinaryTree(TreeNode root) {
    int ans = 1;
    l = r = 0;
    nq[r] = root;
    iq[r++] = 1;
    while (l < r) {
      int size = r - l;
      ans = Math.max(ans, iq[r - 1] - iq[l] + 1);
      for (int i = 0; i < size; i++) {
        TreeNode node = nq[l];
        int id = iq[l++];
        if (node.left != null) {
          nq[r] = node.left;
          iq[r++] = id * 2;
        }
        if (node.right != null) {
          nq[r] = node.right;
          iq[r++] = id * 2 + 1;
        }
      }
    }
    return ans;
  }
}

code4 104. 二叉树的最大深度 111. 二叉树的最小深度

// 求二叉树的最大、最小深度

// 测试链接 : https://leetcode.cn/problems/maximum-depth-of-binary-tree/

// 测试链接 : https://leetcode.cn/problems/minimum-depth-of-binary-tree/

package class036;
// 求二叉树的最大、最小深度
public class Code04_DepthOfBinaryTree {
  // 不提交这个类
  public static class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
  }
  // 测试链接 : https://leetcode.cn/problems/maximum-depth-of-binary-tree/
  public static int maxDepth(TreeNode root) {
    return root == null ? 0 : Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
  }
  // 测试链接 : https://leetcode.cn/problems/minimum-depth-of-binary-tree/
  public int minDepth(TreeNode root) {
    if (root == null) {
      // 当前的树是空树
      return 0;
    }
    if (root.left == null && root.right == null) {
      // 当前root是叶节点
      return 1;
    }
    int ldeep = Integer.MAX_VALUE;
    int rdeep = Integer.MAX_VALUE;
    if (root.left != null) {
      ldeep = minDepth(root.left);
    }
    if (root.right != null) {
      rdeep = minDepth(root.right);
    }
    return Math.min(ldeep, rdeep) + 1;
  }
}

code5 297. 二叉树的序列化与反序列化

// 二叉树先序序列化和反序列化

// 测试链接 : https://leetcode.cn/problems/serialize-and-deserialize-binary-tree/

package class036;
// 二叉树先序序列化和反序列化
// 测试链接 : https://leetcode.cn/problems/serialize-and-deserialize-binary-tree/
public class Code05_PreorderSerializeAndDeserialize {
  // 不提交这个类
  public static class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int v) {
      val = v;
    }
  }
    // 二叉树可以通过先序、后序或者按层遍历的方式序列化和反序列化
    // 但是，二叉树无法通过中序遍历的方式实现序列化和反序列化
    // 因为不同的两棵树，可能得到同样的中序序列，即便补了空位置也可能一样。
    // 比如如下两棵树
    //         __2
    //        /
    //       1
    //       和
    //       1__
    //          \
    //           2
    // 补足空位置的中序遍历结果都是{ null, 1, null, 2, null}
  // 提交这个类
  public class Codec {
    public String serialize(TreeNode root) {
      StringBuilder builder = new StringBuilder();
      f(root, builder);
      return builder.toString();
    }
    void f(TreeNode root, StringBuilder builder) {
      if (root == null) {
        builder.append("#,");
      } else {
        builder.append(root.val + ",");
        f(root.left, builder);
        f(root.right, builder);
      }
    }
    public TreeNode deserialize(String data) {
      String[] vals = data.split(",");
      cnt = 0;
      return g(vals);
    }
    // 当前数组消费到哪了
    public static int cnt;
    TreeNode g(String[] vals) {
      String cur = vals[cnt++];
      if (cur.equals("#")) {
        return null;
      } else {
        TreeNode head = new TreeNode(Integer.valueOf(cur));
        head.left = g(vals);
        head.right = g(vals);
        return head;
      }
    }
  }
}

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

// 利用先序与中序遍历序列构造二叉树

// 测试链接 : https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

package class036;
// 二叉树按层序列化和反序列化
// 测试链接 : https://leetcode.cn/problems/serialize-and-deserialize-binary-tree/
public class Code06_LevelorderSerializeAndDeserialize {
  // 不提交这个类
  public static class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int v) {
      val = v;
    }
  }
  // 提交这个类
  // 按层序列化
  public class Codec {
    public static int MAXN = 10001;
    public static TreeNode[] queue = new TreeNode[MAXN];
    public static int l, r;
    public String serialize(TreeNode root) {
      StringBuilder builder = new StringBuilder();
      if (root != null) {
        builder.append(root.val + ",");
        l = 0;
        r = 0;
        queue[r++] = root;
        while (l < r) {
          root = queue[l++];
          if (root.left != null) {
            builder.append(root.left.val + ",");
            queue[r++] = root.left;
          } else {
            builder.append("#,");
          }
          if (root.right != null) {
            builder.append(root.right.val + ",");
            queue[r++] = root.right;
          } else {
            builder.append("#,");
          }
        }
      }
      return builder.toString();
    }
    public TreeNode deserialize(String data) {
      if (data.equals("")) {
        return null;
      }
      String[] nodes = data.split(",");
      int index = 0;
      TreeNode root = generate(nodes[index++]);
      l = 0;
      r = 0;
      queue[r++] = root;
      while (l < r) {
        TreeNode cur = queue[l++];
        cur.left = generate(nodes[index++]);
        cur.right = generate(nodes[index++]);
        if (cur.left != null) {
          queue[r++] = cur.left;
        }
        if (cur.right != null) {
          queue[r++] = cur.right;
        }
      }
      return root;
    }
    private TreeNode generate(String val) {
      return val.equals("#") ? null : new TreeNode(Integer.valueOf(val));
    }
  }
}

code7 958. 二叉树的完全性检验

// 验证完全二叉树

// 测试链接 : https://leetcode.cn/problems/check-completeness-of-a-binary-tree/

1)无左有右 flase

2)孩子不全开始 必须都是叶子结点，否则false

package class036;
import java.util.HashMap;
// 利用先序与中序遍历序列构造二叉树
// 测试链接 : https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
public class Code07_PreorderInorderBuildBinaryTree {
  // 不提交这个类
  public static class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int v) {
      val = v;
    }
  }
  // 提交如下的方法
  public static TreeNode buildTree(int[] pre, int[] in) {
    if (pre == null || in == null || pre.length != in.length) {
      return null;
    }
    HashMap<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < in.length; i++) {
      map.put(in[i], i);
    }
    return f(pre, 0, pre.length - 1, in, 0, in.length - 1, map);
  }
  public static TreeNode f(int[] pre, int l1, int r1, int[] in, int l2, int r2, HashMap<Integer, Integer> map) {
    if (l1 > r1) {
      return null;
    }
    TreeNode head = new TreeNode(pre[l1]);
    if (l1 == r1) {
      return head;
    }
    int k = map.get(pre[l1]);
    // pre : l1(........)[.......r1]
    // in  : (l2......)k[........r2]
    // (...)是左树对应，[...]是右树的对应
    head.left = f(pre, l1 + 1, l1 + k - l2, in, l2, k - 1, map);
    head.right = f(pre, l1 + k - l2 + 1, r1, in, k + 1, r2, map);
    return head;
  }
}

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

// 求完全二叉树的节点个数

// 测试链接 : https://leetcode.cn/problems/count-complete-tree-nodes/

package class036;
// 验证完全二叉树
// 测试链接 : https://leetcode.cn/problems/check-completeness-of-a-binary-tree/
public class Code08_CompletenessOfBinaryTree {
  // 不提交这个类
  public static class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
  }
  // 提交以下的方法
  // 如果测试数据量变大了就修改这个值
  public static int MAXN = 101;
  public static TreeNode[] queue = new TreeNode[MAXN];
  public static int l, r;
  public static boolean isCompleteTree(TreeNode h) {
    if (h == null) {
      return true;
    }
    l = r = 0;
    queue[r++] = h;
    // 是否遇到过左右两个孩子不双全的节点
    boolean leaf = false;
    while (l < r) {
      h = queue[l++];
      if ((h.left == null && h.right != null) || (leaf && (h.left != null || h.right != null))) {
        return false;
      }
      if (h.left != null) {
        queue[r++] = h.left;
      }
      if (h.right != null) {
        queue[r++] = h.right;
      }
      if (h.left == null || h.right == null) {
        leaf = true;
      }
    }
    return true;
  }
}

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

// 求完全二叉树的节点个数

// 测试链接 : https://leetcode.cn/problems/count-complete-tree-nodes/

package class036;
// 求完全二叉树的节点个数
// 测试链接 : https://leetcode.cn/problems/count-complete-tree-nodes/
public class Code09_CountCompleteTreeNodes {
  // 不提交这个类
  public static class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
  }
  // 提交如下的方法
  public static int countNodes(TreeNode head) {
    if (head == null) {
      return 0;
    }
    return f(head, 1, mostLeft(head, 1));
  }
  // cur : 当前来到的节点
  // level :  当前来到的节点在第几层
  // h : 整棵树的高度，不是cur这棵子树的高度
  // 求 : cur这棵子树上有多少节点
  public static int f(TreeNode cur, int level, int h) {
    if (level == h) {
      return 1;
    }
    if (mostLeft(cur.right, level + 1) == h) {
      // cur右树上的最左节点，扎到了最深层
      return (1 << (h - level)) + f(cur.right, level + 1, h);
    } else {
      // cur右树上的最左节点，没扎到最深层
      return (1 << (h - level - 1)) + f(cur.left, level + 1, h);
    }
  }
  // 当前节点是cur，并且它在level层
  // 返回从cur开始不停往左，能扎到几层
  public static int mostLeft(TreeNode cur, int level) {
    while (cur != null) {
      level++;
      cur = cur.left;
    }
    return level - 1;
  }
}


文章标签：
算法
关键词：
题目算法
二叉树算法
dp算法
树dp算法
题目树算法
日星月云
目录
相关文章
东方睿赢
|
16天前
|
存储 算法 Java
Java中，树与图的算法涉及二叉树的前序、中序、后序遍历以及DFS和BFS搜索。
【6月更文挑战第21天】Java中，树与图的算法涉及二叉树的前序、中序、后序遍历以及DFS和BFS搜索。二叉树遍历通过访问根、左、右子节点实现。DFS采用递归遍历图的节点，而BFS利用队列按层次访问。以下是简化的代码片段：[Java代码略]
东方睿赢
19 4
反季雪
|
12天前
|
存储 算法
【数据结构和算法】--- 二叉树（4）--二叉树链式结构的实现（2）
【数据结构和算法】--- 二叉树（4）--二叉树链式结构的实现（2）
反季雪
12 0
反季雪
|
12天前
|
存储 算法 Linux
【数据结构和算法】---二叉树（1）--树概念及结构
【数据结构和算法】---二叉树（1）--树概念及结构
反季雪
12 0
你都不懂
|
2天前
|
算法
刷算法Leetcode---9（二叉树篇Ⅲ）
刷算法Leetcode---9（二叉树篇Ⅲ）
你都不懂
9 3
weixin_836869520
|
16天前
|
算法 Java 机器人
Java数据结构与算法：AVL树
Java数据结构与算法：AVL树
weixin_836869520
20 6
反季雪
|
12天前
|
算法 分布式数据库
【数据结构和算法】--- 二叉树（5）--二叉树OJ题
【数据结构和算法】--- 二叉树（5）--二叉树OJ题
反季雪
9 1
线上0.5
|
11天前
|
机器学习/深度学习 数据采集 存储
算法金 | 决策树、随机森林、bagging、boosting、Adaboost、GBDT、XGBoost 算法大全
**摘要：** 这篇文章介绍了决策树作为一种机器学习算法，用于分类和回归问题，通过一系列特征测试将复杂决策过程简化。文章详细阐述了决策树的定义、构建方法、剪枝优化技术，以及优缺点。接着，文章讨论了集成学习，包括Bagging、Boosting和随机森林等方法，解释了它们的工作原理、优缺点以及如何通过结合多个模型提高性能和泛化能力。文中特别提到了随机森林和GBDT（XGBoost）作为集成方法的实例，强调了它们在处理复杂数据和防止过拟合方面的优势。最后，文章提供了选择集成学习算法的指南，考虑了数据特性、模型性能、计算资源和过拟合风险等因素。
线上0.5
12 0
算法金 | 决策树、随机森林、bagging、boosting、Adaboost、GBDT、XGBoost 算法大全
24k纯甄
|
13天前
|
算法
【C/数据结构与算法】：二叉树经典OJ
【C/数据结构与算法】：二叉树经典OJ
24k纯甄
12 0
【C/数据结构与算法】：二叉树经典OJ
小森ai小小贾
|
15天前
|
机器学习/深度学习 算法
梯度提升树GBDT系列算法
在Boosting集成算法当中，我们逐一建立多个弱评估器（基本是决策树），并且下一个弱评估器的建立方式依赖于上一个弱评估器的评估结果，最终综合多个弱评估器的结果进行输出。
小森ai小小贾
15 2
朝阳39
|
1天前
|
算法 JavaScript
JS 【详解】二叉树（含二叉树的前、中、后序遍历技巧和算法实现）
JS 【详解】二叉树（含二叉树的前、中、后序遍历技巧和算法实现）
朝阳39
9 0

热门文章

最新文章

  • 1
    【机器学习】K-means和KNN算法有什么区别？
  • 2
    【人工智能】机器学习算法综述及常见算法详解
  • 3
    【机器学习】在使用K-means聚类算法时，如何选择K的值？
  • 4
    【机器学习】为什么K-means算法使用欧式距离度量？
  • 5
    经典机器学习算法——Pagerank算法（一）
  • 6
    高性价比发文典范——101种机器学习算法组合革新骨肉瘤预后模型
  • 7
    深度学习|改进两阶段鲁棒优化算法i-ccg
  • 8
    【机器学习】比较朴素贝叶斯算法与逻辑回归算法
  • 9
    【机器学习】描述K-means算法的步骤
  • 10
    【智能算法】11种混沌映射算法+2种智能算法示范【鲸鱼WOA、灰狼GWO算法】
  • 1
    算法人生（1）：从“强化学习”看如何“战胜拖延”
    58
  • 2
    理解并应用机器学习算法：决策树
    60
  • 3
    【机器学习】在使用K-means聚类算法时，如何选择K的值？
    166
  • 4
    【机器学习】为什么K-means算法使用欧式距离度量？
    151
  • 5
    【机器学习】描述K-means算法的步骤
    97
  • 6
    【机器学习】K-means和KNN算法有什么区别？
    283
  • 7
    C语言易混淆、简单算法、结构体题目练习、常见关键字总结-2
    26
  • 8
    C语言易混淆、简单算法、结构体题目练习、常见关键字总结-1
    27
  • 9
    图搜索算法详解
    45
  • 10
    R语言实现蒙特卡洛模拟算法
    46

    • 相关课程

    更多
  • 智能运维赛（复赛）：利用数据和算法，快速定位系统异常并进行根因分析
  • 智能创作赛（复赛）：相册应用中的视频故事生成算法介绍
  • 智能创作赛（初赛）：相册应用中的故事生成算法介绍
  • 相册服务中的故事生成算法介绍
  • Go语言核心编程 - 数据结构和算法
  • 神经网络概览及算法详解

    • 相关电子书

    更多
  • 数据+算法定义新世界
  • 袋鼠云基于实时计算的反黄牛算法
  • Alink：基于Apache Flink的算法平台

    • 相关实验场景

    更多
  • 使用Swing算法实现商品推荐
    • 下一篇
    部署LAMP环境（Alibaba Cloud Linux 3）