二叉树相关算法与概念总结（基本完善）...
二叉树的相关概念
叶子节点：把没有子节点的节点叫做叶子节点或者叶节点。
例如上图中的G、H、I、J、K、L都是叶子节点
根节点：相对的，没有父节点的节点叫做根节点
例如上图中的E
平衡二叉树 ： 二叉树中任意一个节点的左右子树的高度相差不能大于1。
完全二叉树： 叶子节点都在最底下两层，最后一层的叶子节点都靠左排列，并且除了最后一层，其他层的节点个数都要达到最大，这种二叉树叫做完全二叉树。
完全二叉树可以存储在数组中，不至于浪费空间。
二叉树算法与题目
二叉树的深度复制
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21class TreeNode {
int value;
TreeNode left;
TreeNode right;
public TreeNode(int x) {
value = x;
}
}
//TreeNode newRoot;
public TreeNode copyTree(TreeNode root){
if(root == null){
return null;
}
TreeNode newRoot = new TreeNode(root.value);
newRoot.left = copyTree(root.left);
newRoot.right = copyTree(root.right);
return newRoot;
}二叉树的最大深度
1
2
3
4
5
6
7public int maxDepth(TreeNode root) {
if (root == null) return 0;
int left = maxDepth(root.left);
int right = maxDepth(root.right);
return Math.max(left, right) + 1;
}二叉树的最小深度 111. 二叉树的最小深度
思路：递归的调用搜索左右子树的最小深度，然后返回最小的
1
2
3
4
5
6
7
8
9
10public int minDepth(TreeNode root){
//思路：递归的调用minDepth
if(root == null){
return Integer.MAX_VALUE;
}
if(root.left == null && root.right == null){
return 1;
}
return Math.min(minDepth(root.left),minDepth(root.right)) + 1;
}二叉树中节点的个数
1
2
3
4
5
6
7
8
9
10
11public int numOfTreeNode(TreeNode root){
//思路 递归的调用自己找左子树中的节点数，和右子树中的节点数，最后 返回当前节点的所有节点数，包括它自己，所以要+1
if(root == null) return 0;
int left = numOfTreeNode(root.left);
int right = numOfTreeNode(root.right);
return left + right + 1;
}二叉树中叶子节点的个数
1
2
3
4
5
6
7
8
9
10public int numOfChildNode(TreeNode root) {
//找二叉树的叶子节点，也就是没有子节点的节点，要考虑它的左子树和右子树同时不存在的情况
if (root == null) return 0;
if (root.left == null && root.right == null) { //如果发现该节点的左子树和右子树同时为空，那么这个为叶子节点，所以返回1
return 1;
}
return numOfTreeNode(root.left) + numOfTreeNode(root.right);
}二叉树中第k层节点的个数（不是很懂）
1
2
3
4
5
6
7
8
9
10
11
12
13
14//二叉树中第k层节点的个数
public int numsOfKLevelTreeNode(TreeNode root, int k) {
//考虑K层
if (root == null | k < 1)
return 0;
if (k == 1) {
return 1;
}
int numsLeft = numsOfKLevelTreeNode(root.left, k - 1);
int numsRight = numsOfKLevelTreeNode(root.right, k - 1);
return numsLeft + numsRight;
}判断二叉树是否是平衡二叉树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20//判断二叉树是否是平衡二叉树
public boolean isBalanced(TreeNode root) {
//后序遍历+剪枝（从底至顶）
//对二叉树做后序遍历，从底至顶返回子树深度，若判断某子树不是平衡树则"剪枝"，直接向上返回
return maxDepth(root) != -1;
}
//返回的是子树的深度
int maxDepth(TreeNode root) {
if (root == null) return 0;
int left = maxDepth(root.left);
int right = maxDepth(root.right);
if (left == -1 | right == -1 || Math.abs(left - right) > 1)
return -1;
return Math.max(left, right) + 1;
}判断二叉树是否是完全二叉树
第一种思路，依据完全二叉树的特性：它可以很好的存放在数组中，也就是连续的
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27//判断一棵树是否是完全二叉树
int n = 0, p = 0;
public boolean isCompleteTree(TreeNode root) {
//思路一：根据完全二叉树可以使用数组来存这个特性来进行解答
//k 存的是当前节点的编号 n为搜索到的节点个数，p是当前最大节点编号值
//搜索过程：
//1. 从根节点开始搜索 此时 k = 1
//2. 遍历左子树 右子树 左子树的的2 * k ,右子树的为 2*k + 1
//3. 在这个过程中添加终止条件
//4. root == null 遍历到了叶子节点，直接返回
//5. 节点数 n += 1；
//6. 当前最大的节点编号值 p = Math.max(p,k)
dfs(root, 1);
return n == p;
}
public void dfs(TreeNode root, int k) {
//前序遍历
if (root == null) return; //叶子节点
n++;
p = Math.max(p, k);
dfs(root.left, 2 * k);
dfs(root.right, 2 * k + 1);
}思路二：广度优先遍历｜BFS｜层序遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36public boolean isCompleteTree(TreeNode root) {
//思路一：根据完全二叉树可以使用数组来存这个特性来进行解答
//k 存的是当前节点的编号 n为搜索到的节点个数，p是当前最大节点编号值
//搜索过程：
//1. 从根节点开始搜索 此时 k = 1
//2. 遍历左子树 右子树 左子树的的2 * k ,右子树的为 2*k + 1
//3. 在这个过程中添加终止条件
//4. root == null 遍历到了叶子节点，直接返回
//5. 节点数 n += 1；
//6. 当前最大的节点编号值 p = Math.max(p,k)
/*
dfs(root, 1);
return n == p;
*/
//思路二：广度优先遍历｜层序遍历｜使用队列
//问题转换为：什么时候是不完全呢？其实就是出现null节点之后又出现了节点，如果是完全则最后一个null节点之后就结束遍历了
Queue<TreeNode> queue = new LinkedList<>();
boolean reachNull = false;
queue.add(root);
while(!queue.isEmpty()){
TreeNode t = queue.poll();
if(t == null){
reachNull = true;
}else{
if(reachNull) return false; //在访问到null节点之后还有节点，直接返回false
queue.add(t.left);
queue.add(t.right);
}
}
return true;
}
两个二叉树是否完全相同 100. 相同的树
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15public boolean isSameTree(TreeNode p, TreeNode q) {
if (p == null && q == null) {
return true;
} else if (p == null || q == null) {
return false;
}
if (p.val != q.val) {
return false;
}
boolean left = isSameTree(p.left, q.left);
boolean right = isSameTree(p.right, q.right);
return left && right;
}两个二叉树是否互为镜像 101. 对称二叉树
1
2
3
4
5
6
7
8
9
10
11
12
13public boolean isMirror(TreeNode t1, TreeNode t2) {
if (t1 == null && t2 == null) {
return true;
} else if (t1 == null || t2 == null) {
return false;
}
if (t1.val != t2.val) {
return false;
}
return isMirror(t1.left, t2.right) && isMirror(t1.right, t2.left);
}力扣上那道题还是要写左右两边的，本质是一样的。
翻转二叉树or镜像二叉树 226. 翻转二叉树
1
2
3
4
5
6
7
8
9
10
11public TreeNode invertTree(TreeNode root) {
if(root == null)
return null;
TreeNode left = invertTree(root.left);
TreeNode right = invertTree(root.right);
root.left = right;
root.right = left;
return root;
}两个二叉树的最低公共祖先节点 236. 二叉树的最近公共祖先
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19//求两个二叉树的最低公共祖先节点
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
//递归的查看有几种情况
//1.
if (root == null || root == p || root == q) return root;
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
if (left == null && right == null) return null;
if (left == null) return right;
if (right == null) return left;
return root;
}
二叉树的遍历
二叉树的前序遍历 144. 二叉树的前序遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17//二叉树的前序遍历
ArrayList<Integer> list;
public List<Integer> preorderTraversal(TreeNode root) {
list = new ArrayList<>();
recur(root);
return list;
}
private void recur(TreeNode root) {
if (root == null) return;
list.add(root.val);
recur(root.left);
recur(root.right);
}迭代解法-使用辅助栈
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24public List<Integer> preorderTraversal(TreeNode root) {
/* list = new ArrayList<>();
recur(root);
return list;*/
//使用辅助栈
if(root == null)
return new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
list = new ArrayList<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
list.add(node.val);
if (node.right != null) stack.push(node.right);
if (node.left != null) stack.push(node.left);
}
return list;
}二叉树的中序遍历 94. 二叉树的中序遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17//二叉树的中序遍历
ArrayList<Integer> list;
public List<Integer> inorderTraversal(TreeNode root) {
list = new ArrayList<>();
recur(root);
return list;
}
private void recur(TreeNode root){
if(root == null) return;
recur(root.left);
list.add(root.val);
recur(root.right);
}二叉树的后序遍历 145. 二叉树的后序遍历
简单的遍历有手就行
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16//二叉树的后序遍历
ArrayList<Integer> list;
public List<Integer> postorderTraversal(TreeNode root) {
list = new ArrayList<>();
recur(root);
return list;
}
private void recur(TreeNode root) {
if (root == null) return;
recur(root.left);
recur(root.right);
list.add(root.val);
}前序遍历和后序遍历构造二叉树 889. 根据前序和后序遍历构造二叉树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31//前序遍历和后序遍历构造二叉树
int[] preorder;
HashMap<Integer, Integer> dic = new HashMap<>();
public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {
this.preorder = preorder;
for (int i = 0; i < postorder.length; i++) {
dic.put(postorder[i], i);
}
return recur(0, 0, postorder.length - 1);
}
private TreeNode recur(int pre_root, int post_left, int post_right) {
if (post_left > post_right) return null;
TreeNode root = new TreeNode(preorder[pre_root]);
if (post_left == post_right)
return root;
//注意这个idx表示的在后序遍历中左子树根节点的位置
int idx = dic.get(preorder[pre_root + 1]);
root.left = recur(pre_root + 1, post_left, idx);
root.right = recur(pre_root + idx - post_left + 2, idx + 1, post_right - 1);
return root;
}从中序与后序遍历序列构造二叉树 106. 从中序与后序遍历序列构造二叉树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30//从中序与后序遍历序列构造二叉树
int[] postorder;
HashMap<Integer, Integer> dic = new HashMap<>();
public TreeNode buildTree(int[] inorder, int[] postorder) {
this.postorder = postorder;
for (int i = 0; i < inorder.length; i++) {
dic.put(inorder[i], i);
}
return recur(postorder.length - 1, 0, inorder.length - 1);
}
private TreeNode recur(int post_root, int in_left, int in_right) {
if (in_left > in_right) return null;
TreeNode root = new TreeNode(postorder[post_root]);
int idx = dic.get(postorder[post_root]);
//递归的遍历
root.left = recur(post_root - (in_right - idx) - 1, in_left, idx - 1);
root.right = recur(post_root - 1, idx + 1, in_right);
return root;
}从前序与中序遍历序列构造二叉树 105. 从前序与中序遍历序列构造二叉树 剑指 Offer 07. 重建二叉树
查看K神的代码，需要注意的是这题和本文中上面第17题的前提条件是树中不含重复元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28//从前序与中序遍历序列构造二叉树
int[] preorder;
HashMap<Integer, Integer> dic = new HashMap<>();
public TreeNode buildTree(int[] preorder, int[] inorder) {
this.preorder = preorder;
for (int i = 0; i < inorder.length; i++) {
dic.put(inorder[i], i);
}
return recur(0, 0, inorder.length - 1);
}
private TreeNode recur(int pre_root, int in_left, int in_right) {
if (in_left > in_right) return null;
TreeNode root = new TreeNode(preorder[pre_root]);
//从中序遍历中获取当前根节点的index
int idx = dic.get(preorder[pre_root]);
//左子树的根，左边界，右边界
root.left = recur(pre_root + 1, in_left, idx - 1);
root.right = recur(pre_root + (idx - in_left) + 1, idx + 1, in_right);
return root;
}在二叉搜索树中插入节点（在 一篇文章搞定面试中的二叉树题目(java实现) 中作者写在二叉树中插入节点，其实二叉树中插入节点的只要遍历找到子树中有null的地方插入就好了，可以插入的位置很多）701. 二叉搜索树中的插入操作
由于二叉搜索（查找）树的特点，所以要做比较。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23//二叉搜索树中的插入操作
public TreeNode insertIntoBST(TreeNode root, int val) {
if (root == null) return new TreeNode(val);
if (root.val == val) return root;
TreeNode node = root;
while (node != null) {
if (node.val < val) {
if (node.right == null) {
node.right = new TreeNode(val);
break;
}
node = node.right;
} else { //node.val > val
if (node.left == null) {
node.left = new TreeNode(val);
break;
}
node = node.left;
}
}
return root;
}输入一个二叉树和一个整数，打印出二叉树中节点值的和等于输入整数所有的路径 剑指 Offer 34. 二叉树中和为某一值的路径
参考K神，这道题属于回溯法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22//输入一个二叉树和一个整数，打印出二叉树中节点值的和等于输入整数所有的路径
LinkedList<List<Integer>> res = new LinkedList<>();
LinkedList<Integer> path = new LinkedList<>();
public List<List<Integer>> pathSum(TreeNode root, int target) {
recur(root, target);
return res;
}
private void recur(TreeNode root, int target) {
if (root == null) return;
path.add(root.val);
target -= root.val;
if (root.left == null && root.right == null && (target == 0))
res.add(new LinkedList(path));
recur(root.left, target);
recur(root.right, target);
path.removeLast();
}二叉查找树中搜索区间 11 · 二叉查找树中搜索区间
描述
给定一个二叉查找树和范围
[k1, k2]。按照升序返回给定范围内的节点值。解题思路参考：
九章算法 - 帮助更多程序员找到好工作，硅谷顶尖IT企业工程师实时在线授课为你传授面试技巧
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26//二叉查找树中搜索区间
ArrayList<Integer> res;
public List<Integer> searchRange(TreeNode root, int k1, int k2) {
// write your code here
res = new ArrayList<>();
recur(root, k1, k2);
return res;
}
private void recur(TreeNode root, int k1, int k2) {
if (root == null) return;
if (k1 < root.val) {
recur(root.left, k1, k2);
}
if (k1 <= root.val && k2 >= root.val) {
res.add(root.val);
}
if (k2 > root.val) {
recur(root.right, k1, k2);
}
}二叉树的层次遍历（BFS）102. 二叉树的层序遍历
一般BFS借助队列queue实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28//二叉树的层序遍历
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if(root == null) return res;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
int size = queue.size();
List<Integer> tmp = new ArrayList<>();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
tmp.add(node.val);
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
}
res.add(tmp);
}
return res;
}序列化二叉树 剑指 Offer 37. 序列化二叉树
前中后序遍历，存储的二叉树结构不是完整的，一个序列可能表示多个二叉树
困难题目，参考K神代码：
1 | public class Codec { |
二叉树内两个节点的最长距离 543. 二叉树的直径
这道题据说是《编程之美》上面的
可以考虑为求二叉树左右子树的最大深度然后+1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18//二叉树内两个节点的最长距离
int res;
public int diameterOfBinaryTree(TreeNode root) {
res = 0;
depth(root);
return res;
}
private int depth(TreeNode root) {
if (root == null) return 0;
int left = depth(root.left);
int right = depth(root.right);
res = Math.max(res, left + right);
return Math.max(left, right) + 1;
}不同的二叉树 96. 不同的二叉搜索树
呃，动态规划…
1
2
3
4
5
6
7
8
9
10
11
12
13//不同的二叉树
public int numTrees(int n) {
int[] G = new int[n + 1];
G[0] = 1;
G[1] = 1;
for (int i = 2; i <= n; ++i) {
for (int j = 1; j <= i; ++j) {
G[i] += G[j - 1] * G[i - j];
}
}
return G[n];
}判断二叉树是否是合法的二叉查找树（BST）98. 验证二叉搜索树
当时有个面试官给我出了这道题，我当时的解法就很简单，中序遍历+验证递增数组
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22//判断二叉树是否是合法的二叉查找树
List<Integer> list;
public boolean isValidBST(TreeNode root) {
list = new ArrayList<>();
recur(root);
for (int i = 1; i < list.size(); i++) {
if (list.get(i) <= list.get(i - 1)) {
return false;
}
}
return true;
}
private void recur(TreeNode root) {
if (root == null) return;
recur(root.left);
list.add(root.val);
recur(root.right);
}想要提升效率的话，应该在遍历二叉树的时候提前终止
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16//提前终止的返回
long pre = Long.MIN_VALUE;
public boolean isValidBST(TreeNode root){
return inorder(root);
}
private boolean inorder(TreeNode root){
if(root == null) return true;
if(!inorder(root.left)) return false;
if(root.val <= pre) return false;
pre = root.val;
return inorder(root.right);
}
总结
二叉树的难点不是前中后序遍历或者层序遍历，而是根据二叉树的数据结构特点来进行改编的一些题目，因为二叉树大多涉及递归，所以要仔细想清楚每一步要做什么。
现在时间对于我来说是很少、很紧迫的，有些题目都是理解了尽量少文字解释，但这样有诸多不好，像维特根斯坦说的：“我的语言的极限是我世界的极限”，而后不忙了还需要逐步完善。
参考
- 二叉树相关算法与概念总结（基本完善）
- 王争《数据结构与算法之美》
- 一篇文章搞定面试中的二叉树题目(java实现)
- 《算法》(第4版)(图灵出品) [Algorithms, Fourth Edition]
- 力扣剑指题目下Krahets 的解答
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 既往不恋！
wechat
alipay
相关推荐
评论
WalineGitalk