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

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

2023-12-21 88
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 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算法
题目树算法
日星月云
目录
相关文章
胖咕噜的稞达鸭
|
2月前
|
存储 算法
算法入门：专题二---滑动窗口(长度最小的子数组）类型题目攻克！
给定一个正整数数组和目标值target，找出总和大于等于target的最短连续子数组长度。利用滑动窗口（双指针）优化，维护窗口内元素和，通过单调性避免重复枚举，时间复杂度O(n)。当窗口和满足条件时收缩左边界，更新最小长度，最终返回结果。
胖咕噜的稞达鸭
156 3
陌陌谣
|
2月前
|
存储 机器学习/深度学习 监控
网络管理监控软件的 C# 区间树性能阈值查询算法
针对网络管理监控软件的高效区间查询需求，本文提出基于区间树的优化方案。传统线性遍历效率低，10万条数据查询超800ms，难以满足实时性要求。区间树以平衡二叉搜索树结构，结合节点最大值剪枝策略，将查询复杂度从O(N)降至O(logN+K)，显著提升性能。通过C#实现，支持按指标类型分组建树、增量插入与多维度联合查询，在10万记录下查询耗时仅约2.8ms，内存占用降低35%。测试表明，该方案有效解决高负载场景下的响应延迟问题，助力管理员快速定位异常设备，提升运维效率与系统稳定性。
陌陌谣
222 4
胖咕噜的稞达鸭
|
2月前
|
存储 算法 编译器
算法入门：剑指offer改编题目：查找总价格为目标值的两个商品
给定递增数组和目标值target，找出两数之和等于target的两个数字。利用双指针法，left从头、right从尾向中间逼近，根据和与target的大小关系调整指针，时间复杂度O(n)，空间复杂度O(1)。找不到时返回{-1,-1}。
胖咕噜的稞达鸭
159 4
陌陌谣
|
5月前
|
监控 算法 安全
基于 C# 基数树算法的网络屏幕监控敏感词检测技术研究
随着数字化办公和网络交互迅猛发展，网络屏幕监控成为信息安全的关键。基数树（Trie Tree）凭借高效的字符串处理能力，在敏感词检测中表现出色。结合C#语言，可构建高时效、高准确率的敏感词识别模块，提升网络安全防护能力。
陌陌谣
145 2
技术自由圈/原疯狂创客圈
|
7月前
|
存储 机器学习/深度学习 算法
KMP、Trie树 、AC自动机‌ ，三大算法实现 优雅 过滤 netty 敏感词
KMP、Trie树 、AC自动机‌ ，三大算法实现 优雅 过滤 netty 敏感词
技术自由圈/原疯狂创客圈
558 8
KMP、Trie树 、AC自动机‌ ，三大算法实现 优雅 过滤 netty 敏感词
陌陌谣
|
7月前
|
监控 算法 数据处理
基于 C++ 的 KD 树算法在监控局域网屏幕中的理论剖析与工程实践研究
本文探讨了KD树在局域网屏幕监控中的应用，通过C++实现其构建与查询功能，显著提升多维数据处理效率。KD树作为一种二叉空间划分结构，适用于屏幕图像特征匹配、异常画面检测及数据压缩传输优化等场景。相比传统方法，基于KD树的方案检索效率提升2-3个数量级，但高维数据退化和动态更新等问题仍需进一步研究。未来可通过融合其他数据结构、引入深度学习及开发增量式更新算法等方式优化性能。
陌陌谣
197 17
陌陌谣
|
7月前
|
存储 监控 算法
局域网上网记录监控的 C# 基数树算法高效检索方案研究
在企业网络管理与信息安全领域，局域网上网记录监控是维护网络安全、规范网络行为的关键举措。随着企业网络数据量呈指数级增长，如何高效存储和检索上网记录数据成为亟待解决的核心问题。基数树（Trie 树）作为一种独特的数据结构，凭借其在字符串处理方面的卓越性能，为局域网上网记录监控提供了创新的解决方案。本文将深入剖析基数树算法的原理，并通过 C# 语言实现的代码示例，阐述其在局域网上网记录监控场景中的具体应用。
陌陌谣
179 7
JustDoIT技术吧
|
6月前
|
机器学习/深度学习 算法 搜索推荐
决策树算法如何读懂你的购物心理？一文看懂背后的科学
"你为什么总能收到刚好符合需求的商品推荐？你有没有好奇过，为什么刚浏览过的商品就出现了折扣通知？
JustDoIT技术吧
214 0
蚝油菜花
|
9月前
|
人工智能 算法 语音技术
Video-T1：视频生成实时手术刀！清华腾讯「帧树算法」终结闪烁抖动
清华大学与腾讯联合推出的Video-T1技术，通过测试时扩展（TTS）和Tree-of-Frames方法，显著提升视频生成的连贯性与文本匹配度，为影视制作、游戏开发等领域带来突破性解决方案。
蚝油菜花
320 4
Video-T1：视频生成实时手术刀！清华腾讯「帧树算法」终结闪烁抖动
修己xj
|
9月前
|
存储 算法 Java
算法系列之数据结构-二叉树
树是一种重要的非线性数据结构，广泛应用于各种算法和应用中。本文介绍了树的基本概念、常见类型（如二叉树、满二叉树、完全二叉树、平衡二叉树、B树等）及其在Java中的实现。通过递归方法实现了二叉树的前序、中序、后序和层次遍历，并展示了具体的代码示例和运行结果。掌握树结构有助于提高编程能力，优化算法设计。
修己xj
305 10
算法系列之数据结构-二叉树

热门文章

最新文章

  • 1
    【机器学习算法篇】K-近邻算法
  • 2
    《数据之美》：图结构的精妙世界与算法实践
  • 3
    从零掌握贪心算法Java版：LeetCode 10题实战解析（上）
  • 4
    【水下图像增强融合算法】基于融合的水下图像与视频增强研究（Matlab代码实现）
  • 5
    go-dongle v1.1.7 发布，新增 SM4 国密分组对称加密算法支持
  • 6
    go-dongle v1.1.7 发布，新增 SM4 国密分组对称加密算法支持
  • 7
    set_map的实现+set/map加持秒杀高频算法题锻炼算法思维
  • 8
    HNSW算法实战：用分层图索引替换k-NN暴力搜索
  • 9
    基于python智能推荐算法的全屋定制系统
  • 10
    电脑监控管理中的 C# 哈希表进程资源索引算法
  • 1
    当“爆款书”遇上大数据：出版业的老路，正在被算法改写
    175
  • 2
    当AI成为航天员的“大脑外设”：智能算法如何优化人类的长期太空旅行
    151
  • 3
    电脑监控管理中的 C# 哈希表进程资源索引算法
    183
  • 4
    HNSW算法实战：用分层图索引替换k-NN暴力搜索
    192
  • 5
    基于python智能推荐算法的全屋定制系统
    204
  • 6
    使用哈里斯角Harris和SIFT算法来实现局部特征匹配（Matlab代码实现）
    174
  • 7
    基于导向滤波的暗通道去雾算法在灰度与彩色图像可见度复原中的研究（Matlab代码实现）
    179
  • 8
    【水下图像增强融合算法】基于融合的水下图像与视频增强研究（Matlab代码实现）
    259
  • 9
    结合多种启发式解码方法的混合多目标进化算法，用于解决带工人约束的混合流水车间调度问题（Matlab代码实现）
    166
  • 10
    【基于TTNRBO优化DBN回归预测】基于瞬态三角牛顿-拉夫逊优化算法（TTNRBO）优化深度信念网络（DBN）数据回归预测研究（Matlab代码实现）
    152

    • 相关课程

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

    • 相关电子书

    更多
  • 数据+算法定义新世界
  • 袋鼠云基于实时计算的反黄牛算法
  • Alink：基于Apache Flink的算法平台
    • 下一篇
    「直播预告」Streaming Lakehouse Meetup EP.2｜Paimon × StarRocks 共话实时湖仓