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

简介: 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;
  }
}


目录
打赏
0
0
0
0
25
分享
相关文章
基于 C++ 的 KD 树算法在监控局域网屏幕中的理论剖析与工程实践研究
本文探讨了KD树在局域网屏幕监控中的应用,通过C++实现其构建与查询功能,显著提升多维数据处理效率。KD树作为一种二叉空间划分结构,适用于屏幕图像特征匹配、异常画面检测及数据压缩传输优化等场景。相比传统方法,基于KD树的方案检索效率提升2-3个数量级,但高维数据退化和动态更新等问题仍需进一步研究。未来可通过融合其他数据结构、引入深度学习及开发增量式更新算法等方式优化性能。
87 17
局域网上网记录监控的 C# 基数树算法高效检索方案研究
在企业网络管理与信息安全领域,局域网上网记录监控是维护网络安全、规范网络行为的关键举措。随着企业网络数据量呈指数级增长,如何高效存储和检索上网记录数据成为亟待解决的核心问题。基数树(Trie 树)作为一种独特的数据结构,凭借其在字符串处理方面的卓越性能,为局域网上网记录监控提供了创新的解决方案。本文将深入剖析基数树算法的原理,并通过 C# 语言实现的代码示例,阐述其在局域网上网记录监控场景中的具体应用。
70 7
Video-T1:视频生成实时手术刀!清华腾讯「帧树算法」终结闪烁抖动
清华大学与腾讯联合推出的Video-T1技术,通过测试时扩展(TTS)和Tree-of-Frames方法,显著提升视频生成的连贯性与文本匹配度,为影视制作、游戏开发等领域带来突破性解决方案。
143 4
Video-T1:视频生成实时手术刀!清华腾讯「帧树算法」终结闪烁抖动
|
4月前
|
算法系列之数据结构-二叉树
树是一种重要的非线性数据结构,广泛应用于各种算法和应用中。本文介绍了树的基本概念、常见类型(如二叉树、满二叉树、完全二叉树、平衡二叉树、B树等)及其在Java中的实现。通过递归方法实现了二叉树的前序、中序、后序和层次遍历,并展示了具体的代码示例和运行结果。掌握树结构有助于提高编程能力,优化算法设计。
102 9
 算法系列之数据结构-二叉树
|
4月前
|
算法系列之数据结构-Huffman树
Huffman树(哈夫曼树)又称最优二叉树,是一种带权路径长度最短的二叉树,常用于信息传输、数据压缩等方面。它的构造基于字符出现的频率,通过将频率较低的字符组合在一起,最终形成一棵树。在Huffman树中,每个叶节点代表一个字符,而每个字符的编码则是从根节点到叶节点的路径所对应的二进制序列。
121 3
 算法系列之数据结构-Huffman树
【C++数据结构——树】二叉树的遍历算法(头歌教学实验平台习题) 【合集】
本任务旨在实现二叉树的遍历,包括先序、中序、后序和层次遍历。首先介绍了二叉树的基本概念与结构定义,并通过C++代码示例展示了如何定义二叉树节点及构建二叉树。接着详细讲解了四种遍历方法的递归实现逻辑,以及层次遍历中队列的应用。最后提供了测试用例和预期输出,确保代码正确性。通过这些内容,帮助读者理解并掌握二叉树遍历的核心思想与实现技巧。
209 2
文件管理系统中基于 Python 语言的二叉树查找算法探秘
在数字化时代,文件管理系统至关重要。本文探讨了二叉树查找算法在文件管理中的应用,并通过Python代码展示了其实现过程。二叉树是一种非线性数据结构,每个节点最多有两个子节点。通过文件名的字典序构建和查找二叉树,能高效地管理和检索文件。相较于顺序查找,二叉树查找每次比较可排除一半子树,极大提升了查找效率,尤其适用于海量文件管理。Python代码示例包括定义节点类、插入和查找函数,展示了如何快速定位目标文件。二叉树查找算法为文件管理系统的优化提供了有效途径。
114 5
分享一些提高二叉树遍历算法效率的代码示例
这只是简单的示例代码,实际应用中可能还需要根据具体需求进行更多的优化和处理。你可以根据自己的需求对代码进行修改和扩展。
如何提高二叉树遍历算法的效率?
选择合适的遍历算法,如按层次遍历树时使用广度优先搜索(BFS),中序遍历二叉搜索树以获得有序序列。优化数据结构,如使用线索二叉树减少空指针判断,自定义节点类增加辅助信息。利用递归与非递归的特点,避免栈溢出问题。多线程并行遍历提高速度,注意线程安全。缓存中间结果,避免重复计算。预先计算并存储信息,提高遍历效率。综合运用这些方法,提高二叉树遍历算法的效率。
184 5

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等

登录插画

登录以查看您的控制台资源

管理云资源
状态一览
快捷访问