本站消息
必要掌握的二叉树题目（附OJ链接+Java参考代码）
发布于2020-11-19 20:40 阅读(1693) 评论(0) 点赞(26) 收藏(1)
必须掌握的二叉树题目
1.二叉树前序遍历
递归与非递归都得会写，建议去OJ自己测一下，如果只是复习，直接看下面代码也行。
思路就不写了，OJ链接里有很多优秀的题解，写的通俗易懂有深度。
下面的题目同样如此。
OJ链接
https://leetcode-cn.com/problems/binary-tree-preorder-traversal/
描述
给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
提示：
树中节点数目在范围 [0, 100] 内
-100 <= Node.val <= 100
进阶：递归算法很简单，你可以通过迭代算法完成吗？
示例
示例 1：
输入：root = [1,null,2,3]
输出：[1,2,3]
示例 2：
输入：root = []
输出：[]
示例 3：
输入：root = [1]
输出：[1]
示例 4：
输入：root = [1,2]
输出：[1,2]
示例 5：
输入：root = [1,null,2]
输出：[1,2]
代码
递归
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new LinkedList<>();
prevOrder(root, res);
return res;
}
private void prevOrder(TreeNode root, List<Integer> res) {
if (root == null) {
return;
}
res.add(root.val);
prevOrder(root.left, res);
prevOrder(root.right, res);
}
}
迭代
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new LinkedList<>();
if (root != null) {
Deque<TreeNode> stack = new ArrayDeque<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode cur = stack.pop();
res.add(cur.val);
if (cur.right != null) {
stack.push(cur.right);
}
if (cur.left != null) {
stack.push(cur.left);
}
}
}
return res;
}
}
2.二叉树中序遍历
OJ链接
https://leetcode-cn.com/problems/binary-tree-inorder-traversal/
描述
给定一个二叉树的根节点 root ，返回它的 中序 遍历。
提示：
树中节点数目在范围 [0, 100] 内
-100 <= Node.val <= 100
进阶: 递归算法很简单，你可以通过迭代算法完成吗？
示例
示例 1：
输入：root = [1,null,2,3]
输出：[1,3,2]
示例 2：
输入：root = []
输出：[]
示例 3：
输入：root = [1]
输出：[1]
示例 4：
输入：root = [1,2]
输出：[2,1]
示例 5：
输入：root = [1,null,2]
输出：[1,2]
代码
递归
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new LinkedList<>();
inOrder(root, res);
return res;
}
private void inOrder(TreeNode root, List<Integer> res) {
if (root == null) {
return;
}
inOrder(root.left, res);
res.add(root.val);
inOrder(root.right, res);
}
}
迭代
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new LinkedList<>();
if (root != null) {
Deque<TreeNode> stack = new ArrayDeque<>();
while (!stack.isEmpty() || root != null) {
if (root != null) {
stack.push(root);
root = root.left;
} else {
root = stack.pop();
res.add(root.val);
root = root.right;
}
}
}
return res;
}
}
3.二叉树后序遍历
OJ链接
https://leetcode-cn.com/problems/binary-tree-postorder-traversal/
描述
给定一个二叉树，返回它的 后序 遍历。
进阶: 递归算法很简单，你可以通过迭代算法完成吗？
示例
输入: [1,null,2,3]
1
\
2
/
3
输出: [3,2,1]
代码
递归
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new LinkedList<>();
postOrder(root, res);
return res;
}
private void postOrder(TreeNode root, List<Integer> res) {
if (root == null) {
return;
}
postOrder(root.left, res);
postOrder(root.right, res);
res.add(root.val);
}
}
迭代
首先是一段比较简单的代码，结果是符合后序遍历的，但是严格上说，这个遍历的顺序并不是后序遍历，因为借助了头插入addFirst，只是答案符合要求。在要求不是很严格的情况下可以使用。还有另外的写法。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
LinkedList<Integer> res = new LinkedList<>();
if (root != null) {
Deque<TreeNode> stack = new ArrayDeque<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode cur = stack.pop();
res.addFirst(cur.val);
if (cur.left != null) {
stack.push(cur.left);
}
if (cur.right != null) {
stack.push(cur.right);
}
}
}
return res;
}
}
这个写法就比较遵循正常后序遍历的顺序了：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new LinkedList<>();
if (root != null) {
Deque<TreeNode> stack = new ArrayDeque<>();
stack.push(root);
TreeNode prev = root;
while (!stack.isEmpty()) {
root = stack.peek();
if (root.left != null && prev != root.left && prev != root.right) {
//如果当前节点左节点不为空，并且之前遍历的节点不等于左右子节点，说明左节点没遍历过
stack.push(root.left);
} else if (root.right != null && prev != root.right) {
//如果右节点没遍历过
stack.push(root.right);
} else {
res.add(stack.pop().val);
prev = root;
}
}
}
return res;
}
}
4.相同的树
OJ链接
https://leetcode-cn.com/problems/same-tree/
描述
给定两个二叉树，编写一个函数来检验它们是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
示例
示例 1:
输入: 1 1
/ \ / \
2 3 2 3
[1,2,3], [1,2,3]
输出: true
示例 2:
输入: 1 1
/ \
2 2
[1,2], [1,null,2]
输出: false
示例 3:
输入: 1 1
/ \ / \
2 1 1 2
[1,2,1], [1,1,2]
输出: false
代码
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
if (p == null && q == null) {
return true;
}
if (p == null || q == null || p.val != q.val) {
return false;
}
return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}
}
5.另一个树的子树
OJ链接
https://leetcode-cn.com/problems/subtree-of-another-tree/
描述
给定两个非空二叉树 s 和 t，检验 s 中是否包含和 t 具有相同结构和节点值的子树。s 的一个子树包括 s 的一个节点和这个节点的所有子孙。s 也可以看做它自身的一棵子树。
示例
示例 1:
给定的树 s:
3
/ \
4 5
/ \
1 2
给定的树 t：
4
/ \
1 2
返回 true，因为 t 与 s 的一个子树拥有相同的结构和节点值。
示例 2:
给定的树 s：
3
/ \
4 5
/ \
1 2
/
0
给定的树 t：
4
/ \
1 2
返回 false。
代码
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public boolean isSubtree(TreeNode s, TreeNode t) {
if (s == null) {
return false;
}
return isSameTree(s, t) || isSubtree(s.left, t) || isSubtree(s.right, t);
}
private boolean isSameTree(TreeNode p, TreeNode q) {
if (p == null && q == null) {
return true;
}
if (p == null || q == null || p.val != q.val) {
return false;
}
return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}
}
6.二叉树的最大深度
OJ链接
https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/
描述
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例
给定二叉树 [3,9,20,null,null,15,7]，
3
/ \
9 20
/ \
15 7
返回它的最大深度 3 。
代码
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int maxDepth(TreeNode root) {
return root == null ? 0 : Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}
}
7.判断一棵二叉树是否是平衡二叉树
OJ链接
https://leetcode-cn.com/problems/balanced-binary-tree/submissions/
描述
给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
提示：
树中的节点数在范围 [0, 5000] 内
-104 <= Node.val <= 104
示例
示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：true
示例 2：
输入：root = [1,2,2,3,3,null,null,4,4]
输出：false
示例 3：
输入：root = []
输出：true
代码
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public boolean isBalanced(TreeNode root) {
return judge(root) != -1;
}
private int judge(TreeNode root) {
if (root == null) {
return 0;
}
int left = judge(root.left);
if (left == -1) {
return -1;
}
int right = judge(root.right);
if (right == -1) {
return -1;
}
return Math.abs(left - right) >= 2 ? -1 : Math.max(left, right) + 1;
}
}
8.对称二叉树
OJ链接
https://leetcode-cn.com/problems/symmetric-tree/
描述
给定一个二叉树，检查它是否是镜像对称的。
进阶：
你可以运用递归和迭代两种方法解决这个问题吗？
示例
例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
1
/ \
2 2
/ \ / \
3 4 4 3
但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
1
/ \
2 2
\ \
3 3
代码
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isSymmetric(TreeNode root) {
return judge(root, root);
}
private boolean judge(TreeNode p, TreeNode q) {
if (p == null && q == null) {
return true;
}
if (p == null || q == null || p.val != q.val) {
return false;
}
return judge(p.left, q.right) && judge(p.right, q.left);
}
}
9.二叉树遍历
OJ链接
描述
编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。
例如如下的先序遍历字符串： ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空树。建立起
此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。
输入描述:
输入包括1行字符串，长度不超过100。
输出描述:
可能有多组测试数据，对于每组数据，
输出将输入字符串建立二叉树后中序遍历的序列，每个字符后面都有一个空格。
每个输出结果占一行。
示例
输入
abc##de#g##f###
输出
c b e g d f a
代码
先来一个不构建二叉树的：
import java.util.Scanner;
import java.util.Deque;
import java.util.ArrayDeque;
public class Main{
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
while (input.hasNext()) {
String str = input.next();
Deque<Character> stack = new ArrayDeque<>();
for (char c : str.toCharArray()) {
if (c == '#') {
if (!stack.isEmpty()) {
System.out.print(stack.pop() + " ");
}
} else {
stack.push(c);
}
}
System.out.println();
}
input.close();
}
}
再来个更符合题目要求的，先构建二叉树，再遍历
import java.util.Scanner;
class TreeNode {
char val;
TreeNode left;
TreeNode right;
public TreeNode(char val) {
this.val = val;
}
}
public class Main{
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
while (input.hasNext()) {
String str = input.next();
initIndex();
TreeNode root = createTreeByPrevOrder(str);
inOrder(root);
}
input.close();
}
private static int index;
private static void initIndex() {
index = 0;
}
// 通过前序遍历构建二叉树，返回根节点
private static TreeNode createTreeByPrevOrder(String str) {
TreeNode node = null;
if (str.charAt(index) != '#') {
node = new TreeNode(str.charAt(index));
index++;
node.left = createTreeByPrevOrder(str);
node.right = createTreeByPrevOrder(str);
} else {
index++;
}
return node;
}
private static void inOrder(TreeNode root) {
if (root == null) {
return;
}
inOrder(root.left);
System.out.print(root.val + " ");
inOrder(root.right);
}
}
10.二叉树的层序遍历
OJ链接
https://leetcode-cn.com/problems/binary-tree-level-order-traversal/
描述
给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。
示例
二叉树：[3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回其层次遍历结果：
[
[3],
[9,20],
[15,7]
]
代码
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new LinkedList<>();
if (root == null) {
return res;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
List<Integer> cur = new LinkedList<>();
for (int size = queue.size(); size > 0; size--) {
TreeNode node = queue.poll();
cur.add(node.val);
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
res.add(cur);
}
return res;
}
}
11.二叉树的最近公共祖先
OJ链接
描述
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先
且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
说明:
所有节点的值都是唯一的。
p、q 为不同节点且均存在于给定的二叉树中。
示例
示例 1:
输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出: 3
解释: 节点 5 和节点 1 的最近公共祖先是节点 3。
示例 2:
输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出: 5
解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。
代码
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null || root == p || root == q) {
return root;
}
TreeNode leftFind = lowestCommonAncestor(root.left, p, q);
TreeNode rightFind = lowestCommonAncestor(root.right, p, q);
if (leftFind == null) {
return rightFind;
}
if (rightFind == null) {
return leftFind;
}
return root;
}
}
12.二叉搜索树与双向链表
OJ链接
https://leetcode-cn.com/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof/
描述
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。
特别地，我们希望可以就地完成转换操作。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。
代码
/*
// Definition for a Node.
class Node {
public int val;
public Node left;
public Node right;
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val,Node _left,Node _right) {
val = _val;
left = _left;
right = _right;
}
};
*/
class Solution {
Node prev;
Node head;
public Node treeToDoublyList(Node root) {
if (root == null) {
return null;
}
inOrder(root);
head.left = prev;
prev.right = head;
return head;
}
private void inOrder(Node root) {
if (root == null) {
return;
}
inOrder(root.left);
if (prev == null) {
head = root;
} else {
prev.right = root;
}
root.left = prev;
prev = root;
inOrder(root.right);
}
}
13.从前序与中序遍历构建二叉树
OJ链接
https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
描述
根据一棵树的前序遍历与中序遍历构造二叉树。
注意:
你可以假设树中没有重复的元素。
示例
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：
3
/ \
9 20
/ \
15 7
代码
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
return build(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
}
private TreeNode build(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd) {
if (preStart > preEnd) {
return null;
}
int rootVal = preorder[preStart];
int index = -1;
for (int i = inStart; i <= inEnd; i++) {
if (inorder[i] == rootVal) {
index = i;
break;
}
}
int leftSize = index - inStart;
TreeNode root = new TreeNode(rootVal);
root.left = build(preorder, preStart + 1, preStart + leftSize, inorder, inStart, index - 1);
root.right = build(preorder, preStart + leftSize + 1, preEnd, inorder, index + 1, inEnd);
return root;
}
}
14.从中序与后序遍历序列构建二叉树
OJ链接
https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
描述
根据一棵树的中序遍历与后序遍历构造二叉树。
注意:
你可以假设树中没有重复的元素。
示例
例如，给出
中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]
返回如下的二叉树：
3
/ \
9 20
/ \
15 7
代码
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode buildTree(int[] inorder, int[] postorder) {
return build(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1);
}
private TreeNode build(int[] inorder, int inStart, int inEnd, int[] postorder, int postStart, int postEnd) {
if (postStart > postEnd) {
return null;
}
int rootVal = postorder[postEnd];
int index = -1;
for (int i = inStart; i <= inEnd; i++) {
if (inorder[i] == rootVal) {
index = i;
break;
}
}
int leftSize = index - inStart;
TreeNode root = new TreeNode(rootVal);
root.left = build(inorder, inStart, index - 1, postorder, postStart, postStart + leftSize - 1);
root.right = build(inorder, index + 1, inEnd, postorder, postStart + leftSize, postEnd - 1);
return root;
}
}
所属网站分类: 技术文章 > 博客
作者：长这么胖
链接：http://www.javaheidong.com/blog/article/841/5b128f7bda85221eaa44/
来源：java黑洞网
任何形式的转载都请注明出处,如有侵权 一经发现 必将追究其法律责任
26
0
收藏该文
昵称:
评论内容：(最多支持255个字符)
---无人问津也好，技不如人也罢，你都要试着安静下来，去做自己该做的事，而不是让内心的烦躁、焦虑，坏掉你本来就不多的热情和定力
程序员的那些事(new)
更多>
电子书(new)
博客(new)
视频教程(new)
问答(new)
游戏(new)
其他资源(new)