鼎泰网
leetcode面试题之二叉树
创始人
2024-03-21 06:23:16
0次

文章目录

    • 144. 二叉树的前序遍历
    • 94. 二叉树的中序遍历
    • 145. 二叉树的后序遍历
    • 102. 二叉树的层序遍历
    • 层次遍历其他题目
      • 107. 二叉树的层序遍历 II
      • 199. 二叉树的右视图
      • 637. 二叉树的层平均值
      • 429. N 叉树的层序遍历
      • 515. 在每个树行中找最大值
      • 116. 填充每个节点的下一个右侧节点指针
      • 104. 二叉树的最大深度
      • 111. 二叉树的最小深度
      • 559. N 叉树的最大深度
    • 226. 翻转二叉树
    • 101. 对称二叉树

144. 二叉树的前序遍历

题目：给你二叉树的根节点 root ，返回它节点值的 前序 遍历。

链接：https://leetcode.cn/problems/binary-tree-preorder-traversal/

思路:前序遍历：根左右

  1. 递归
  2. 非递归
    （1）栈
    （2）根节点先入栈，再是右节点入栈，再左节点

代码：

递归：

public List preorderTraversal(TreeNode root) {List res = new ArrayList<>();preorder(root, res);return res;}public void preorder(TreeNode root, List res) {if (root == null) return;res.add(root.val);preorder(root.left, res);preorder(root.right, res);}

非递归：

public List preorderTraversal(TreeNode root) {Stack st = new Stack<>();List res = new ArrayList<>();if (root != null) st.push(root);while (!st.isEmpty()) {TreeNode node = st.pop();res.add(node.val);if (node.right != null) st.push(node.right);if (node.left != null) st.push(node.left);}return res;}

94. 二叉树的中序遍历

题目：给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。

链接：https://leetcode.cn/problems/binary-tree-inorder-traversal/

思路：中序：左根右
非递归

  1. 根节点不为空，根节点入栈，并继续往左走
  2. 根节点为空，出栈并访问，继续往右走

代码：

public List inorderTraversal(TreeNode root) {List res = new ArrayList<>();Stack st = new Stack<>();while (root != null || !st.isEmpty()) {// 根节点不为空，根节点入栈，继续往左走if (root != null) {st.push(root);root = root.left;}else {// 根节点为空，栈不为空，出栈访问，继续往右走root = st.pop();res.add(root.val);root = root.right;}}return res;}

145. 二叉树的后序遍历

题目：给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。

链接：https://leetcode.cn/problems/binary-tree-postorder-traversal/

思路：后序：左右根
前序：根左右 —> 改为根右左 —> 再反转
反转：Collections.reverse(res);

代码：

public List postorderTraversal(TreeNode root) {List res = new ArrayList<>();Stack st = new Stack<>();// 前序：根左右  ---> 根右左if (root != null) st.push(root);while (!st.isEmpty()) {TreeNode node = st.pop();res.add(node.val);if (node.left != null) st.push(node.left);if (node.right != null) st.push(node.right);}// 反转 根右左 ---> 左右根Collections.reverse(res);return res;}

102. 二叉树的层序遍历

题目：给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）

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

思路：层次遍历：队列

代码：

public List> levelOrder(TreeNode root) {List> res = new ArrayList<>();Queue q = new ArrayDeque<>();// 1. 处理根节点if (root != null) q.add(root);// 2.遍历每层while (!q.isEmpty()) {int n = q.size(); // 记录当层节点数List level = new ArrayList<>(); // 记录当层节点值// 处理当层节点：1.出栈并访问 2.左节点入队 3.右节点入队 for (int i = 0; i < n; i ++) {TreeNode node = q.poll();level.add(node.val);if (node.left != null) q.add(node.left);if (node.right != null) q.add(node.right);}res.add(level);}return res;}

层次遍历其他题目

107. 二叉树的层序遍历 II

题目：自底向上的层序遍历

链接：https://leetcode.cn/problems/binary-tree-level-order-traversal-ii/
思路：层次遍历，最后反转结果

代码：

public List> levelOrderBottom(TreeNode root) {List> res = new ArrayList<>();Queue q = new ArrayDeque<>();if (root != null) q.add(root);while (!q.isEmpty()) {int n = q.size();List level = new ArrayList<>();for (int i = 0; i < n; i ++) {TreeNode node = q.poll();level.add(node.val);if (node.left != null) q.add(node.left);if (node.right != null) q.add(node.right);}res.add(level);}// 反转Collections.reverse(res);return res;}

199. 二叉树的右视图

题目：给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
链接：https://leetcode.cn/problems/binary-tree-right-side-view/
思路：层次遍历，记录每层的最后一个节点值

代码：

public List rightSideView(TreeNode root) {List res = new ArrayList<>();Queue q = new ArrayDeque<>();if (root != null) q.add(root);while (!q.isEmpty()) {int n = q.size();for (int i = 0; i < n; i ++) {TreeNode node = q.poll();// res记录每层的最后一个节点if (i == n - 1) res.add(node.val);if (node.left != null) q.add(node.left);if (node.right != null) q.add(node.right);}}return res;}

637. 二叉树的层平均值

题目：给定一个非空二叉树的根节点 root , 以数组的形式返回每一层节点的平均值。与实际答案相差 10-5 以内的答案可以被接受。
链接：https://leetcode.cn/problems/average-of-levels-in-binary-tree/
思路：层次遍历，每层遍历时，求得节点的sum，一层遍历完成后取平均

代码：

public List averageOfLevels(TreeNode root) {List res = new ArrayList<>();Queue q = new ArrayDeque<>();if (root != null) q.add(root);while (!q.isEmpty()) {int n = q.size(); double sum = 0; // 每层节点求和List level = new ArrayList<>(); for (int i = 0; i < n; i ++) {TreeNode node = q.poll();sum += node.val;if (node.left != null) q.add(node.left);if (node.right != null) q.add(node.right);}// 节点值和去平均后放入resres.add(sum / n);}return res;}

429. N 叉树的层序遍历

题目：给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）
树的序列化输入是用层序遍历，每组子节点都由 null 值分隔
链接：https://leetcode.cn/problems/n-ary-tree-level-order-traversal/
思路：层次遍历

代码：

public List> levelOrder(Node root) {List> res = new ArrayList<>();Queue q = new ArrayDeque<>();if (root != null) q.add(root);while (!q.isEmpty()) {int n = q.size();List level = new ArrayList<>();for (int i = 0; i < n; i ++) {Node node = q.poll();level.add(node.val);// N叉树 遍历入队List children = node.children;for (Node child : children) {if (child != null) q.add(child);}}res.add(level);}return res;}

515. 在每个树行中找最大值

题目：给定一棵二叉树的根节点 root ，请找出该二叉树中每一层的最大值
链接：https://leetcode.cn/problems/find-largest-value-in-each-tree-row/
思路：层次遍历

代码：

public List largestValues(TreeNode root) {List res = new ArrayList<>();Queue q = new ArrayDeque<>();if (root != null) q.add(root);while (!q.isEmpty()) {int n = q.size(), max = Integer.MIN_VALUE;for (int i = 0; i < n; i ++) {TreeNode node = q.poll();max = Math.max(max, node.val);if (node.left != null) q.add(node.left);if (node.right != null) q.add(node.right);}res.add(max);}return res;}

116. 填充每个节点的下一个右侧节点指针

题目：给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点

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

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。初始状态下，所有 next 指针都被设置为 NULL
链接：https://leetcode.cn/problems/populating-next-right-pointers-in-each-node/
思路：层次遍历

​ LinkedList，处理本层第一个节点、非第一个节点、最后一个节点方法不同

代码：

只能使用常量级额外空间
思路简单，但不满足题目条件

public Node connect(Node root) {LinkedList q = new LinkedList<>();if (root == null) return root;q.add(root);while(!q.isEmpty()) {int n = q.size();// 将队列中的元素串联起来Node node = q.get(0);for (int i = 1; i < n; i ++) {node.next = q.get(i);node = q.get(i);}// 遍历每个节点并入队for (int i = 0; i < n; i ++) {node = q.remove();if (node.left != null) q.add(node.left);if (node.right != null) q.add(node.right);}}return root;}

public Node connect(Node root) {Queue q = new LinkedList<>();if (root != null) q.add(root);while (!q.isEmpty()) {int n = q.size();Node node = null;Node nodePre = null;for (int i = 0; i < n; i ++) {// 本层第一个节点if (i == 0) {node = q.poll();nodePre = node;} else {// 本层非第一个节点node = q.poll();nodePre.next = node;nodePre = nodePre.next;}if (node.left != null) q.add(node.left);if (node.right != null) q.add(node.right);}// 本层最后一个节点nodePre.next = null;}return root;}

104. 二叉树的最大深度

题目：给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。说明: 叶子节点是指没有子节点的节点。
链接：https://leetcode.cn/problems/maximum-depth-of-binary-tree/
思路：

层次遍历
递归

代码：

层次遍历：

public int maxDepth(TreeNode root) {int depth= 0;Queue q = new LinkedList<>();if (root != null) q.add(root);while (!q.isEmpty()) {int n = q.size();for (int i = 0; i < n; i ++) {TreeNode node = q.poll();if (node.left != null) q.add(node.left);if (node.right != null) q.add(node.right);}depth ++;}return depth;}

递归：

public int maxDepth(TreeNode root) {if (root == null) return 0;else {int left = maxDepth(root.left);int right = maxDepth(root.right);return Math.max(left, right) + 1;}}

111. 二叉树的最小深度

题目：给定一个二叉树，找出其最小深度。最小深度是从根节点到最近叶子节点的最短路径上的节点数量。说明：叶子节点是指没有子节点的节点
链接：https://leetcode.cn/problems/minimum-depth-of-binary-tree/
思路：层次遍历：当遍历到左右孩子都为空时，说明到达最低点

代码：

递归：

public int minDepth(TreeNode root) {if (root == null) return 0;// 注意是根节点到叶子节点// 比如：如果根节点没有左子树，有右子树，最小深度不为1if (root.left != null && root.right == null) {return 1 + minDepth(root.left);}if (root.left == null && root.right != null) {return 1 + minDepth(root.right);}return 1 + Math.min(minDepth(root.left), minDepth(root.right));}

层次遍历：

public int minDepth(TreeNode root) {int depth = 0;Queue q = new LinkedList<>();if (root != null) q.add(root);while (!q.isEmpty()) {int n = q.size();depth ++;for (int i = 0; i < n; i ++) {root = q.poll();// 当左右孩子都为空时，说明遍历到最低点if (root.left == null && root.right == null) {return depth;}if (root.left != null) q.add(root.left);if (root.right != null) q.add(root.right);}}return depth;}

559. N 叉树的最大深度

题目：给定一个 N 叉树，找到其最大深度。最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。N 叉树输入按层序遍历序列化表示，每组子节点由空值分隔
链接：https://leetcode.cn/problems/maximum-depth-of-n-ary-tree/
思路：类似于二叉树的最大深度
1.递归法
2.迭代法（层次遍历）

代码：

递归

public int maxDepth(Node root) {int depth = 0;if (root == null) return depth;for (Node child : root.children){depth = Math.max(depth, maxDepth(child));}return depth + 1;}

层次遍历

public int maxDepth(Node root) {int depth = 0;Queue q = new LinkedList<>();if (root != null) q.add(root);while (!q.isEmpty()) {int n = q.size();depth ++;for (int i = 0; i < n; i ++) {Node node = q.poll();for (Node child : node.children) {if (child != null) q.add(child);}}}return depth;}

226. 翻转二叉树

题目：给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
链接：https://leetcode.cn/problems/invert-binary-tree/
思路：遍历时翻转每个节点的左右子节点，前序、后序、层次都可以，中序要注意避免左右节点翻转两次

代码：层次

public TreeNode invertTree(TreeNode root) {Queue q = new LinkedList<>();if (root != null) q.add(root);while (!q.isEmpty()) {int n = q.size();for (int i = 0; i < n; i ++) {TreeNode node = q.poll();swap(node);if (node.left != null) q.add(node.left);if (node.right != null) q.add(node.right);}}return root;}public void swap(TreeNode node) {TreeNode tmp = node.left;node.left = node.right;node.right = tmp;}

101. 对称二叉树

题目：给你一个二叉树的根节点 root ， 检查它是否轴对称。
链接：https://leetcode.cn/problems/symmetric-tree/
思路
递归：判断节点为空、不为空的情况；不为空时判断节点值是否相同
注意比较对象：
1.左子树的左节点<=>右子树的右节点
2.左子树的右节点<=>右子树的左节点

代码：

递归

public boolean isSymmetric(TreeNode root) {if (root == null) return true;return compare(root.left, root.right);}boolean compare(TreeNode left, TreeNode right) {// 判断节点为空的情况if (left == null && right != null) return false;else if (left != null && right == null) return false;else if (left == null && right == null) return true;// 判断节点不为空的情况else if (left.val != right.val) return false;// 节点不为空，且节点值相等，递归遍历else return compare(left.left, right.right) && compare(left.right, right.left);}

迭代：

public boolean isSymmetric(TreeNode root) {Queue q = new LinkedList<>();if (root == null) return true;q.add(root.left);q.add(root.right);while (!q.isEmpty()) {TreeNode leftNode = q.poll(), rightNode = q.poll();if (leftNode == null && rightNode == null) continue;// false情况合集if (leftNode == null || rightNode == null || leftNode.val != rightNode.val) return false;q.add(leftNode.left);q.add(rightNode.right);q.add(leftNode.right);q.add(rightNode.left);}return true;}

未完待续…

词库加载错误:未能找到文件“E:\highferrum_mysql\Configuration\Dict_Stopwords.txt”。

上一篇：前端处理接口数据常用方法

下一篇：任何对《维护国家安全条例》的攻击抹黑都将以失败告终

相关内容

热门资讯

金证股份（600446）披露拟... 截至2025年12月26日收盘，金证股份（600446）报收于15.75元，较前一交易日下跌0.19...
央行：进一步丰富维护金融市场稳... 每经AI快讯，央行网站12月26日消息，中国人民银行近日发布了《中国金融稳定报告（2025）》。下一...
权威干货来袭！ 2026艺考公...
新华鲜报丨利好跨国公司！这项跨... 新华社北京12月26日电（记者刘开雄、吴雨）中国人民银行、国家外汇管理局12月26日发布通知，在总结...
日元空头共识渐成：2026年或... 随着日本央行最新加息举措未能提振汇率，华尔街对日元的看空情绪再度升温，市场正逐渐形成日元将长期疲软的...
北平锋：民进党当局对所谓“两岸... 12月26日，台湾《中国时报》报道，陆委会近日推动所谓“两岸人民关系条例”四项修正，包含：公务员赴陆...
AI核心产业超万亿，工信部将完... 今年，工业经济顶压前行、向新向优发展，展现强大韧性和活力。 12月25日至26日，全国工业和信息化工...
神州泰岳（300002）披露全... 截至2025年12月26日收盘，神州泰岳（300002）报收于11.37元，较前一交易日上涨0.09...
车企起诉电池企业第一案！吉利旗... 出品 | 搜狐汽车·汽车咖啡馆 作者 | 胡耀丹 2024年底发出的回旋镖，在2025年底向欣旺达疾...
海南产经新观察：封关政策释红利... 中新网海南东方12月26日电 (陈英清)“海南自贸港封关运作顺利实施，政策红利持续释放，南繁水稻制种...