二叉树节点结构
节点定义
class Node<V> {
V value;
Node left;
Node right;
}
用递归和非递归的方式实现二叉树的先序、中序、后序遍历
递归方式
递归遍历的实质利用系统栈
public static void f(Node head) {
if(head == null) {
return;
}
// 1
// 这是递归过程中第一次来到当前节点
// 1
f(head.left);
// 2
// 第二次来到当前节点
// 2
f(head.right);
// 3
// 第三次来到当前节点
// 3
}
前中后序遍历即选择来到当前节点不同时刻
- 前序遍历（选择1）
public static void preOrderRecur(Node head) {
if(head == null) {
return;
}
System.out.println(head.value + " ");
preOrderRecur(head.left);
preOrderRecur(head.right);
}
- 中序遍历（选择2）
public static void inOrderRecur(Node head) {
if(head == null) {
return;
}
inOrderRecur(head.left);
System.out.println(head.value + " ");
inOrderRecur(head.right);
}
- 后序遍历（选择3）
public static void posOrder(Node head) {
if(head == null) {
return;
}
posOrder(head.left);
posOrder(head.right);
System.out.println(head.value + " ");
}
非递归方式
- 前序遍历
1）从栈中弹出一个节点cur
2）打印（处理）cur
3）先右再左（如果有）
4）重新1,2,3步骤直到遍历完整个二叉树
public static void preOrderUnRecur(Node head) {
System.out.print("pre-order：");
if(head != null) {
Stack<Node> stack = new Stack<>();
stack.push(head);
while(!stack.empty()) {
head = stack.pop();
System.out.print(head.value + " ");
if(head.right != null) {
stack.push(head.right);
}
if(head.left != null) {
stack.push(head.left);
}
}
}
System.out.println();
}
- 中序遍历
1）每颗子树整棵树左边界进栈
2）依次弹出的过程中，打印弹出节点的值
3）对弹出节点的右树进行1操作
4）重复1,2,3步骤直到遍历完整个二叉树（栈为空）
public static void inOrderUnRecur(Node head) {
System.out.println("in-order：");
if(head != null) {
Stack<Node> stack = new Stack<>();
while(!stack.isEmpty() || head != null) {
if(head != null) {
stack.push(head);
head = head.left;
} else {
head = stack.pop();
System.out.print(head.value + " ");
head = head.right;
}
}
}
System.out.println();
}
- 后序遍历
1）从栈中弹出一个节点cur
2）cur放入收集栈中
3）先左再右压入栈中（如果有）
4）重新1,2,3步骤直到遍历完整个二叉树（即栈为空）
public static void posOrderUnRecur(Node head) {
System.out.println("pos-order");
if(head != null) {
Stack<Node> s1 = new Stack<>();
Stack<Node> s2 = new Stack<>();
s1.push(head);
while(!s1.isEmpty()) {
head = s1.pop();
s2.push(head);
if(head.left != null) {
s1.push(head.left);
}
if(head.right != null) {
s1.push(head.right);
}
}
while(!s2.isEmpty()) {
System.out.print(s2.pop().value + " ");
}
System.out.println();
}
}
直观的打印一颗二叉树
public static void printTree(Node head) {
System.out.println("Bianry Tree：");
printInOrder(head, 0, "H", 17);
System.out.println();
}
public static void printInOrder(Node head, int height, String to, int len) {
if(head == null) {
return null;
}
printInOrder(head.right, height - 1, "v", len);
String val = to + head.value + to;
int lenM = val.length();
int lenL = (len - lenM) / 2;
int lenR = len - lenM - lenL;
val = getSpace(lenL) + val + getSpace(lenR);
System.out.println(getSpace(height * len) + val);
printInOrder(head.left, hight + 1, "^", len);
}
public static String getSpace(int num) {
String space = "";
StringBuffer buf = new StringBuffer("");
for(int i = 0; i < num; i++) {
buf.append(space);
}
return buf.toString();
}
如何完成二叉树的宽度优先遍历
思想
层序遍历，通过队列先进先出的特点，先将当前层的节点全部放入队列中，依次弹出节点，并添加节点的子节点（下一层节点）到队列中，直到遍历完整棵树，这样就能实现宽度优先遍历。
步骤
层序遍历：
- 先将头节点放入队列中
- 从队列中弹出一个元素
- 将弹出元素存在的子节点放入队列中（先左再右）
- 重复2，3步直到队列为空
代码实现
public static void w(Node head) {
if(head == null) {
return null;
}
Queue<Node> queue = new LinkedList<>();
queue.add(head);
while(!queue.isEmpty()) {
Node cur = queue.poll();
System.out.println(cur.value);
if(cur.left != null) {
queue.add(cur.left);
}
if(cur.right != null) {
queue.add(cur.right);
}
}
}
二叉树的层序遍历(宽度优先遍历)
题目描述
给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]
思路
在宽度优先的基础上，保存当前层的节点个数以及向队列添加新节点时记录下一层的节点个数，通过记录的节点个数遍历每一层。
代码实现
public List<List<Integer>> levelOrder(TreeNode root) {
if(root == null) {
return new ArrayList<List<Integer>>();
}
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
List<List<Integer>> res = new ArrayList<>();
List<Integer> temp = new ArrayList<>();
int curLevelNodes = 1;
int next = 0;
while(!queue.isEmpty()) {
if(curLevelNodes > 0) {
TreeNode cur = queue.poll();
temp.add(cur.val);
--curLevelNodes;
if(cur.left != null) {
queue.add(cur.left);
++next;
}
if(cur.right != null) {
queue.add(cur.right);
++next;
}
} else {
curLevelNodes = next;
res.add(temp);
temp = new ArrayList<>();
next = 0;
}
}
res.add(temp);
return res;
}
分析
时间复杂度：O(N)
空间复杂度：O(N)
求一棵二叉树的宽度
题目描述
给你一棵二叉树的根节点 root ，返回树的 最大宽度 。
树的 最大宽度 是所有层中最大的 宽度 。
思路
基本步骤和bfs差不多，但需要多维护一个节点和其对应层数的hashMap、当前层数的宽度
步骤
- 先将头节点放入队列中，并在hashMap中设置其对应层数为1
- 从队列中弹出一个元素
- 将弹出元素存在的子节点放入队列中（先左再右），添加子节点时需要向hashMap中添加当前节点对应的层数，即父节点层数+1
- 如果当前节点对应的层数 大于 当前层数(即当前已在下一层)，重新记录宽度和当前层数
- 重复2，3步直到队列为空
代码实现
public static int getMaxWidth(Node head) {
if(head == null) {
return 0;
}
int maxWidth = 0;
int curWidth = 0;
int curLevel = 0;
Queue<Node> queue = new LinkedList<>();
HashMap<Node, Integer> levelMap = new HashMap<>();
queue.add(head);
levelMap.put(head, 1);
Node node = null;
Node left = null;
Node right = null;
while(!queue.isEmpty()) {
node = queue.poll();
left = node.left;
right = node.right;
if(left != null) {
queue.add(left);
levelMap.put(left, levelMap.get(node) + 1);
}
if(right != null) {
queue.add(right);
levelMap.put(right, levelMap.get(node) + 1);
}
if(levelMap.get(node) > curLevel) {
curWidth = 0;
curLevel = levelMap.get(node);
} else {
curWidth++;
}
maxWidth = Math.max(maxWidth, curWidth);
}
return maxWidth;
}
二叉树最大宽度
题目描述
给你一棵二叉树的根节点 root ，返回树的 最大宽度 。
树的 最大宽度 是所有层中最大的 宽度 。
每一层的 宽度 被定义为该层最左和最右的非空节点（即，两个端点）之间的长度。将这个二叉树视作与满二叉树结构相同，两端点间会出现一些延伸到这一层的 null 节点，这些 null 节点也计入长度。
题目数据保证答案将会在 32 位 带符号整数范围内。
输入：root = [1,3,2,5,3,null,9]
输出：4
解释：最大宽度出现在树的第 3 层，宽度为 4 (5,3,null,9) 。
思路
- 先将头节点放入队列中，并在indexMap中设置其对应index为0，当前层节点个数为1
- 从队列中弹出一个元素
- 将弹出元素存在的子节点放入队列中（先左再右），添加子节点时需要向indexMap中添加当前节点对应的index，即左节点为父节点的index * 2 +1，右节点为父节点的index * 2 + 2，并更新最左index和最右index
- 遍历完当前层节点，更新最大宽度并重新赋初值最左index和最右index
- 重复2，3，4步直到队列为空
代码实现
public int widthOfBinaryTree(TreeNode root) {
if(root == null) {
return 0;
}
if(root.left == null && root.right == null) {
return 1;
}
int res = Integer.MIN_VALUE;
int curNodes = 1;
int minLeft = Integer.MAX_VALUE;
int maxRight = Integer.MIN_VALUE;
int nextNodes = 0;
HashMap<TreeNode, Integer> indexMap = new HashMap<>();
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
indexMap.put(root, 0);
TreeNode node = null;
TreeNode left = null;
TreeNode right = null;
while(!queue.isEmpty()) {
if(curNodes > 0) {
node = queue.poll();
--curNodes;
left = node.left;
right = node.right;
if(left != null) {
queue.add(left);
int leftIndex = indexMap.get(node) * 2 + 1;
minLeft = Math.min(leftIndex, minLeft);
maxRight = Math.max(leftIndex, maxRight);
indexMap.put(left, leftIndex);
++nextNodes;
}
if(right != null) {
queue.add(right);
int rightIndex = indexMap.get(node) * 2 + 2;
minLeft = Math.min(rightIndex, minLeft);
maxRight = Math.max(rightIndex, maxRight);
indexMap.put(right, rightIndex);
++nextNodes;
}
} else {
curNodes = nextNodes;
nextNodes = 0;
res = Math.max(res, (maxRight - minLeft + 1));
minLeft = Integer.MAX_VALUE;
maxRight = Integer.MIN_VALUE;
}
}
return res;
}
分析
时间复杂度：O(N)
空间复杂度：O(N)
二叉树的相关概念及其实现判断
二叉树种类及其概念
搜索二叉树
搜索二叉树：一颗二叉树，对于其每一颗子树，它的左树节点都比子树根节点小，右树节点都比子树根节点大。
完全二叉树
完全二叉树：一颗二叉树，其除了最后一层以外，其余层都是满的，最后一层不为满时，其节点都是靠左且连续的。
满二叉树
平衡二叉树
如何判断一颗二叉树是搜索二叉树？
题目描述
给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下：
- 节点的左子树只包含 小于 当前节点的数。
- 节点的右子树只包含 大于 当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
思路
二叉搜索树的条件就是在中序遍历的基础上每次比对前一个节点的值和当前节点值的大小，如果存在前一个节点的值大于当前节点即该二叉树不是搜索二叉树。
代码实现
- 递归方式
public long preValue = Long.MIN_VALUE;
public boolean isValidBST(TreeNode root) {
if(root == null) {
return true;
}
boolean isLeftBST = isValidBST(root.left);
if(!isLeftBST) {
return false;
}
if(root.val <= preValue) {
return false;
} else {
preValue = root.val;
}
return isValidBST(root.right);
}
- 非递归方式
public boolean isValidBST(TreeNode head) {
if (head != null) {
long preValue = Long.MIN_VALUE;
Stack<TreeNode> stack = new Stack<>();
while (!stack.isEmpty() || head != null) {
if (head != null) {
stack.push(head);
head = head.left;
} else {
head = stack.pop();
if(head.val <= preValue) {
return false;
} else {
preValue = head.val;
}
head = head.right;
}
}
}
return true;
}
分析
- 递归方式
时间复杂度：O(n)
空间复杂度：O(1)
- 非递归方式
时间复杂度：O(n)
空间复杂度：O(n)
如何判断一颗二叉树是完全二叉树？
题目描述
给定一个二叉树的 root ，确定它是否是一个 完全二叉树 。
在一个 完全二叉树 中，除了最后一个关卡外，所有关卡都是完全被填满的，并且最后一个关卡中的所有节点都是尽可能靠左的。它可以包含 1 到 2h 节点之间的最后一级 h 。
思路
层序遍历整个二叉树：
- 如果当前遍历到的节点，其右子节点不为空而左子节点为空，则该二叉树不可能为完全二叉树
- 在1满足的条件下，如果遍历到某个节点，其左右子节点存在为空的节点，那么在其之后遍历的节点都要是叶子节点。
代码实现
public boolean isCompleteTree(TreeNode root) {
if(root == null) {
return true;
}
Queue<TreeNode> queue = new LinkedList<>();
// 是否遇到左右两个孩子不双全的节点
boolean leaf = false;
TreeNode l = null;
TreeNode r = null;
queue.add(root);
while(!queue.isEmpty()) {
TreeNode node = queue.poll();
l = node.left;
r = node.right;
if(
(leaf && (l != null || r != null))
||
(l == null && r != null)
) {
return false;
}
if(l != null) {
queue.add(l);
}
if(r != null) {
queue.add(r);
} else {
leaf = true;
}
}
return true;
}
分析
时间复杂度：O(N)
空间复杂度：O(N)
二叉树题目套路
以二叉树是否为平衡二叉树为例
平衡二叉树：一颗二叉树，一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
判断是否是一颗平衡二叉树，对于二叉树中的每一个节点都满足下面的条件：
- 节点的左子树是平衡二叉树
- 节点的右子树是平衡二叉树
- 节点的左右子树高度差的绝对值 小于等于 1
套路
- 从左子树要需要的信息
- 从右子树要需要的信息
- 通过左右子树的信息判断节点所代表的当前树是否满足条件
通过套路判断二叉树是否是搜索二叉树
对于二叉树每颗子树都满足下面的条件
- 从左子树要需要的信息：左子树是否是搜索二叉树，左子树最大值
- 从右子树要需要的信息：右子树是否是搜索二叉树，右子树最小值
- 当前节点其左右子树是否都是搜索二叉树，当前节点的值是否大于左子树最大值，小于右子树最小值。
static class ReturnType {
boolean isBst;
int min;
int max;
public ReturnType(boolean isBst, int min, int max) {
this.isBst = isBst;
this.min = min;
this.max = max;
}
}
public boolean isValidBST(TreeNode root) {
return process(root).isBst;
}
public static ReturnType process(TreeNode cur) {
if(cur == null) {
return null;
}
ReturnType leftData = process(cur.left);
ReturnType rightData = process(cur.right);
int min = cur.val;
int max = cur.val;
if(leftData != null) {
min = Math.min(leftData.min, min);
max = Math.max(leftData.max, max);
}
if(rightData != null) {
min = Math.min(rightData.min, min);
max = Math.max(rightData.max, max);
}
// boolean isBst = false;
// if(
// (leftData != null ? (leftData.isBst && leftData.max < cur.val) : true)
// &&
// (rightData != null ? (rightData.isBst && cur.val < rightData.min) : true)
// ) {
// isBst = true;
// }
boolean isBst = true;
if(leftData != null && (!leftData.isBst || leftData.max >= cur.val)) {
isBst = false;
}
if(rightData != null && (!rightData.isBst || cur.val >= rightData.min)) {
isBst = false;
}
return new ReturnType(isBst, min, max);
}
如何判断一颗二叉树是否是满二叉树？
套路
- 从左子树要需要的信息
- 从右子树要需要的信息
- 通过左右子树的信息判断节点所代表的当前树是否满足条件
通过套路判断二叉树是否是满二叉树
遍历二叉树
- 从左子树要需要的信息：左子树的高度，左子树节点数
- 从右子树要需要的信息：右子树的高度，右子树节点数
- 当前节点所在子树的高度为左右子树的高度较大值+1，节点数为左右子树节点数之和+1。
最后判断整个二叉树是否满足节点数 = 2的高度次方 - 1
代码实现
public static boolean isF(TreeNode root) {
if(root == null) {
return true;
}
Info data = process(root);
return data.nodes == (1 << data.height - 1);
}
static class Info {
int height;
int nodes;
public Info(int h, int n) {
height = h;
nodes = n;
}
}
public static Info process(TreeNode root) {
if(root == null) {
return new Info(0, 0);
}
Info leftData = process(root.left);
Info rightData = process(root.right);
int height = Math.max(leftData.height, rightData.height) + 1;
int nodes = leftData.nodes + rightData.nodes + 1;
return new Info(height, nodes);
}
分析
时间复杂度：O(N)
空间复杂度：O(N)
如何判断一颗二叉树是否是平衡二叉树？
题目描述
给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
思路
遍历整个二叉树，对于二叉树中的每一个节点都满足下面的条件：
- 节点的左子树是平衡二叉树
- 节点的右子树是平衡二叉树
- 节点的左右子树高度差的绝对值 小于等于 1
遍历每个节点都返回其所代表的子树是否是平衡二叉树以及其高度
代码实现
static class ReturnType {
public boolean isBalanced;
public int height;
public ReturnType(boolean isBalanced, int height) {
this.isBalanced = isBalanced;
this.height = height;
}
}
public boolean isBalanced(TreeNode root) {
return process(root).isBalanced;
}
public static ReturnType process(TreeNode head) {
if(head == null) {
return new ReturnType(true, 0);
}
ReturnType leftData = process(head.left);
ReturnType rightData = process(head.right);
int height = Math.max(leftData.height, rightData.height) + 1;
boolean isBalanced = leftData.isBalanced && rightData.isBalanced && Math.abs(rightData.height - leftData.height) < 2;
return new ReturnType(isBalanced, height);
}
分析
时间复杂度：O(N)
空间复杂度：O(N)
二叉树的最近公共祖先
题目描述
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。
思路
- 使用HashMap存储子父节点链
- 遍历整个二叉树，设置子父节点对应关系
- 查找节点p的整个祖先链，将祖先链上的每一个元素都放入一个set集合中
- 查找节点q的整个祖先链，遍历到的第一个存在于set中的元素即是最近公共祖先
- 通过最近公共祖先的情况分析
情况一：
情况二：
情况三：
代码实现
- 使用HashMap存储子父节点链
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
HashMap<TreeNode, TreeNode> fatherMap = new HashMap<>();
fatherMap.put(root, root);
process(root, fatherMap);
HashSet<TreeNode> set = new HashSet<>();
TreeNode cur = p;
while(cur != fatherMap.get(cur)) {
set.add(cur);
cur = fatherMap.get(cur);
}
cur = q;
while(cur != fatherMap.get(cur)) {
if(set.contains(cur)) {
return cur;
}
cur = fatherMap.get(cur);
}
return cur;
}
public static void process(TreeNode head, HashMap<TreeNode, TreeNode> fatherMap) {
if(head == null) {
return;
}
fatherMap.put(head.left, head);
fatherMap.put(head.right, head);
process(head.left, fatherMap);
process(head.right, fatherMap);
}
- 通过最近公共祖先的情况分析
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
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 root;
}
return left != null ? left : right;
}
分析
- 使用HashMap存储子父节点链
时间复杂度：O(N)
空间复杂度：O(N)
- 通过最近公共祖先的情况分析
时间复杂度：O(N)
空间复杂度：O(1)
在二叉树中找到一个节点的后继节点
题目描述
现在有一种新的二叉树节点类型如下:
public class Node {
public int value;
public Node left;
public Node right;
public Node parent;
public Node(int val) {
value = val;
}
}
该结构比普通二叉树节点结构多了一个指向父节点的parent指针。
假设有一棵Node类型的节点组成的二叉树，树中每个节点的parent指针都正确地指向自己的父节点，头节点的parent指向null。
只给一个在二叉树中的某个节点node，请实现返回node的后继节点的函数。
在二叉树的中序遍历的序列中， node的下一个节点叫作node的后继节点。
思路
一个节点（x）的后继节点：
- 如果x节点存在右子树，其后继节点即为其右子树的最左节点。
- 如果x节点不存在右子树，其后继节点为 通过祖先链 找到的 该节点是其父节点的左节点的节点，不存在该节点即当前节点为最后一个节点，不存在后继节点。
代码实现
public static Node getSuccessorNode(Node node) {
if(node == null) {
return node;
}
if(node.right != null) {
// x节点存在右子树，其后继节点即为其右子树的最左节点。
return getLeftMost(node.right);
} else {
// 后继节点为 通过祖先链 找到的，
Node parent = node.parent;
while(parent != null && parent.left != node) {
// parent != null 不存在该节点即当前节点为最后一个节点，不存在后继节点
// parent.left != node: 该节点是其父节点的左节点的节点
node = parent;
parent = node.parent;
}
return parent;
}
}
public static Node getLeftMost(Node node) {
while(node.left != null) {
node = node.left;
}
return node;
}
分析
时间复杂度：O(N)
空间复杂度：O(1)
序列化与反序列化二叉树
题目描述
序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。
请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。
思路
统一规定：值为null的节点其值使用#替代
序列化：遍历（前中后）二叉树，每遍历到一个节点将 值_ 添加到序列化字符串中。
反序列化：先将序列化后的字符串转换为一个值数组，根据值数组以及序列化使用的遍历方式，重建二叉树。
代码实现
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
if(root == null) {
return "#_";
}
String res = root.val + "_";
res += serialize(root.left);
res += serialize(root.right);
return res;
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
String[] values = data.split("_");
Queue<String> queue = new LinkedList<>();
for(int i = 0; i != values.length; i++) {
queue.offer(values[i]);
}
return reconPreOrder(queue);
}
public static TreeNode reconPreOrder(Queue<String> queue) {
String value = queue.poll();
if(value.equals("#")) {
return null;
}
TreeNode node = new TreeNode(Integer.valueOf(value));
node.left = reconPreOrder(queue);
node.right = reconPreOrder(queue);
return node;
}
分析
时间复杂度：O(N)
空间复杂度：O(N)
折纸问题
题目描述
请把一段纸条竖着放在桌子上，然后从纸条的下边向上方对折1次，压出折痕后展开。
此时折痕是凹下去的，即折痕突起的方向指向纸条的背面。
如果从纸条的下边向上方连续对折2次，压出折痕后展开，此时有三条折痕，从上到下依次是下折痕、下折痕和上折痕。
给定一个输入参数N，代表纸条都从下边向上方连续对折N次。
请从上到下打印所有折痕的方向。
例如:N=1时，打印: down N=2时，打印: down down up
思路
折痕可以看作是一颗二叉树，而打印折痕的方式就是通过中序遍历这颗二叉树
代码实现
public static viud printAllFolds(int N) {
printProcess(1, N, true); // 最后一个参数代表是否为凹折痕
}
public static void printProcess(int i, int N, boolean down) {
if(i > N) {
return;
}
printProcess(i + 1, N, true);
System.out.println(down ? "down" : "up");
printProcess(i + 1, N, false);
}
分析
时间复杂度：O(N)
空间复杂度：O(1)