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

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

2023-12-21 50
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 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算法
题目树算法
日星月云
目录
相关文章
光明顶阳顶天
|
26天前
|
算法
分享一些提高二叉树遍历算法效率的代码示例
这只是简单的示例代码，实际应用中可能还需要根据具体需求进行更多的优化和处理。你可以根据自己的需求对代码进行修改和扩展。
光明顶阳顶天
44 8
dufadayang
|
29天前
|
存储 缓存 算法
如何提高二叉树遍历算法的效率？
选择合适的遍历算法，如按层次遍历树时使用广度优先搜索（BFS），中序遍历二叉搜索树以获得有序序列。优化数据结构，如使用线索二叉树减少空指针判断，自定义节点类增加辅助信息。利用递归与非递归的特点，避免栈溢出问题。多线程并行遍历提高速度，注意线程安全。缓存中间结果，避免重复计算。预先计算并存储信息，提高遍历效率。综合运用这些方法，提高二叉树遍历算法的效率。
dufadayang
49 5
dufadayang
|
29天前
|
算法
树的遍历算法有哪些？
不同的遍历算法适用于不同的应用场景。深度优先搜索常用于搜索、路径查找等问题；广度优先搜索则在图的最短路径、层次相关的问题中较为常用；而二叉搜索树的遍历在数据排序、查找等方面有重要应用。
dufadayang
27 2
mao29955
|
1月前
|
机器学习/深度学习 JSON 算法
二叉树遍历算法的应用场景有哪些？
【10月更文挑战第29天】二叉树遍历算法作为一种基础而重要的算法，在许多领域都有着不可或缺的应用，它为解决各种复杂的问题提供了有效的手段和思路。随着计算机科学的不断发展，二叉树遍历算法也在不断地被优化和扩展，以适应新的应用场景和需求。
mao29955
32 0
java冯坚持
|
2月前
|
存储 算法 关系型数据库
数据结构与算法学习二一：多路查找树、二叉树与B树、2-3树、B+树、B*树。（本章为了解基本知识即可，不做代码学习）
这篇文章主要介绍了多路查找树的基本概念，包括二叉树的局限性、多叉树的优化、B树及其变体（如2-3树、B+树、B*树）的特点和应用，旨在帮助读者理解这些数据结构在文件系统和数据库系统中的重要性和效率。
java冯坚持
26 0
数据结构与算法学习二一：多路查找树、二叉树与B树、2-3树、B+树、B*树。（本章为了解基本知识即可，不做代码学习）
java冯坚持
|
2月前
|
存储 算法 搜索推荐
数据结构与算法学习十七：顺序储存二叉树、线索化二叉树
这篇文章主要介绍了顺序存储二叉树和线索化二叉树的概念、特点、实现方式以及应用场景。
java冯坚持
28 0
数据结构与算法学习十七：顺序储存二叉树、线索化二叉树
努力学习的小廉
|
2月前
|
存储 算法
【二叉树】—— 算法题
【二叉树】—— 算法题
努力学习的小廉
16 0
【二叉树】—— 算法题
java冯坚持
|
2月前
|
存储 算法
动态规划算法学习一：DP的重要知识点、矩阵连乘算法
这篇文章是关于动态规划算法中矩阵连乘问题的详解，包括问题描述、最优子结构、重叠子问题、递归方法、备忘录方法和动态规划算法设计的步骤。
java冯坚持
122 0
java冯坚持
|
2月前
|
编解码 算法 Java
数据结构与算法学习十九：赫夫曼树树（图文很详细）、赫夫曼编码、应用实践（数据压缩、数据解压）、这一章自我感觉看懂就好。。。
赫夫曼树是一种带权路径长度最短的二叉树，常用于数据压缩和编码。
java冯坚持
49 0
java冯坚持
|
2月前
|
存储 算法
数据结构与算法学习十六：树的知识、二叉树、二叉树的遍历(前序、中序、后序、层次)、二叉树的查找(前序、中序、后序、层次)、二叉树的删除
这篇文章主要介绍了树和二叉树的基础知识，包括树的存储方式、二叉树的定义、遍历方法（前序、中序、后序、层次遍历），以及二叉树的查找和删除操作。
java冯坚持
30 0

热门文章

最新文章

  • 1
    Flink---13、容错机制（检查点（保存、恢复、算法、配置）、状态一致性、端到端精确一次）
  • 2
    openssl中算法的组织方式
  • 3
    JVM内存模型及垃圾回收算法
  • 4
    【算法研究】Bresenham画线算法
  • 5
    九连环的递归算法（C和C++）
  • 6
    【字符串处理算法】删除特定的字符的算法设计及C代码实现
  • 7
    判断一个数字是否为素数的基于C语言的算法
  • 8
    OpenCV 1 图像分割--分水岭算法代码
  • 9
    希尔排序(shellsort)算法实现
  • 10
    缓存、缓存算法(转)
  • 1
    算法人生（1）：从“强化学习”看如何“战胜拖延”
    111
  • 2
    理解并应用机器学习算法：决策树
    136
  • 3
    【机器学习】在使用K-means聚类算法时，如何选择K的值？
    395
  • 4
    【机器学习】为什么K-means算法使用欧式距离度量？
    381
  • 5
    【机器学习】描述K-means算法的步骤
    149
  • 6
    【机器学习】K-means和KNN算法有什么区别？
    621
  • 7
    C语言易混淆、简单算法、结构体题目练习、常见关键字总结-2
    49
  • 8
    C语言易混淆、简单算法、结构体题目练习、常见关键字总结-1
    53
  • 9
    图搜索算法详解
    128
  • 10
    R语言实现蒙特卡洛模拟算法
    300

    • 相关课程

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

    • 相关电子书

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

    • 相关实验场景

    更多
  • 使用Swing算法实现商品推荐
  • RSA密码算法设计与实现
  • RSA非对称加密算法
  • 欧拉图的构造性证明与算法实现
  • 推荐系统入门之使用ALS算法实现打分预测
    • 下一篇
    阿里云无影云电脑免费试用，最长可试用3个月