1、定义
二叉树（binary tree）是指树中节点的度不大于2的有序树
①在二叉树中，一个节点最多有两颗子树，二叉树节点的度<=2
②二叉树的有左右之分，且子树的次序不能颠倒，因此二叉树是有序树
2、二叉树的遍历操作
对于二叉树来说，一共有四种遍历方式
①深度优先遍历（dfs）：先序遍历（根左右），中序遍历（左根右），后序遍历（左右根）
②广度优先遍历（bfs）：层序遍历（将二叉树层层访问）
2.1、先序遍历
先访问根节点，然后递归访问左子树，在递归访问右子树（根左右，就是第一次访问该节点就打印,并且第一个节点一定是根节点）FCADBEHGM
2.2、中序遍历
先递归访问根的左子树，然后是根节点，最后是右子树（左根右，就是第二次访问到该节点时就打印，左子树节点都在根节点左侧，右子树节点在根节点右侧）ACBDFHEMG
2.3、后续遍历
先递归访问左子树，在递归访问右子树，最后是根节点（左右根，就是第三次访问到该节点时就打印）ABDCHMGEF
2.4、层序遍历
FCEADHGBM
2.5、代码实现如下
点击查看代码
public class TraversalBinaryTree {
private static class Node<V> {
public V value;
public Node<V> left;
public Node<V> right;
public Node(V val) {
this.value = val;
}
}
// 先序遍历
public static void pre(Node head) {
if (head == null) {
return;
}
System.out.print(head.value + " ");
pre(head.left);
pre(head.right);
}
// 中序遍历
public static void in(Node head) {
if (head == null) {
return;
}
in(head.left);
System.out.print(head.value + " ");
in(head.right);
}
// 后序遍历
public static void pos(Node head) {
if (head == null) {
return;
}
pos(head.left);
pos(head.right);
System.out.print(head.value + " ");
}
public static void main(String[] args) {
Node head = new Node("F");
Node c = new Node("C");
Node e = new Node("E");
head.left = c;
head.right = e;
c.left = new Node("A");
c.right = new Node("D");
e.left = new Node("H");
e.right = new Node("G");
c.right.left = new Node("B");
e.right.left = new Node("M");
// 先序遍历
pre(head);
System.out.println("\n====================");
// 中序遍历
in(head);
// 后序遍历
System.out.println("\n====================");
pos(head);
}
}
2.6、结论递归序
即每一个节点都会经过3次，不同的打印时机，不同的遍历方式
如果在3个地方都加上打印则得到结果：
F C A A A C D B B B D D C F E H H H E G M M M G G E F
1 2 2 2 1 3 3 3 1
以二叉树各个节点没有重复值为例：首次出现的集合即为（先序遍历）
public static void f(Node head) {
if(head ==null)
return;
// 1
f(head.left);
// 2
f(head.right);
// 3
}
3、常见Coding题
public class TreeNode {
public int val;
public TreeNode left;
public 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;
}
}
3.1、判断两颗二叉树是否相同
测试链接：https://leetcode.com/problems/same-tree
给定两棵二叉树 p 和 q 的根，编写一个函数来检查它们是否相同。 如果两个二叉树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
public class SameTree {
public static boolean isSameTree(TreeNode p, TreeNode q) {
// 一个为空，一个不为空
if (p == null ^ q == null) {
return false;
}
if (p == null && q == null) {
return true;
}
// 根节点相同，与左子树相同，与右子树相同
return p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}
}
3.2、判断一颗树是否是镜面树
将一棵树从中间拆分为左右两颗树:
- 根节点天生镜像
- 左子树的左节点 = 对应右子树的右节点
- 左子树的右节点 = 对应右子树的左节点
测试链接：https://leetcode.com/problems/symmetric-tree
public class SymmetricTree {
/**
* 将一棵树从中间拆分为左右两颗树
* @param root 树的根节点
* @return true / false
*/
public static boolean isSymmetric(TreeNode root) {
return isMirror(root, root);
}
private static boolean isMirror(TreeNode h1, TreeNode h2) {
if (h1 == null ^ h1 == null) {
return false;
}
if (h1 == null && h2 == null) {
return true;
}
// 根节点天生镜像，左子树的左节点 = 对应右子树的右节点，左子树的右节点 = 对应右子树的左节点
return h1.val == h2.val && isMirror(h1.left, h2.right) && isMirror(h1.right, h2.left);
}
}
3.3、计算一颗树的最大深度
给定二叉树的根，返回其最大深度。 二叉树的最大深度是从根节点到最远叶节点的最长路径上的节点数。
左节点最大深度，与右节点最大深度取最大值，加上根节点
测试链接：https://leetcode.com/problems/maximum-depth-of-binary-tree
public class MaximumDepthOfBinaryTree {
public static int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
// 左，右取Max + 根
return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
// int left = maxDepth(root.left);
// int right = maxDepth(root.right);
// int ans = Math.max(left, right) + 1;
// return ans;
}
public static void main(String[] args) {
TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
int depth = maxDepth(root);
System.out.println(depth);
}
}
3.4、根据二叉树的先序和中序数组，重建二叉树
给定两个整数数组 preorder 和 inorder（无重复值），其中 preorder 是二叉树的前序遍历，inorder 是同一棵树的中序遍历，构造并返回二叉树。
3.4.1、分析
找到中序数组in[]中的根节点位置find
中序：find的左边即左树，右边即为右树
先序：L1的下一个位置开始，数（find - L2）个数即左树，剩下的即右树
3.4.2、解决越界
3.4.3、代码实现
测试链接：https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal
点击查看代码
public class ConstructBinaryTreeFromPreorderAndInorderTraversal {
public static TreeNode buildTree(int[] pre, int[] in) {
if (pre == null || in == null || pre.length != in.length) {
return null;
}
Map<Integer, Integer> valueIndexMap = new HashMap<>();
int inLen = in.length;
for (int i = 0; i < inLen; i++) {
valueIndexMap.put(in[i], i);
}
// return doBuild1(pre, 0, pre.length - 1, in, 0, inLen - 1);
// 优化
return doBuild(pre, 0, pre.length - 1, in, 0, inLen - 1, valueIndexMap);
}
/**
* 优化，将中序数组的遍历抽取为 Map<value, index>
*/
public static TreeNode doBuild(int[] pre, int L1, int R1, int[] in, int L2, int R2, Map<Integer, Integer> valueIndexMap) {
// 范围错过去，就是没有树
if (L1 > R1) {
return null;
}
TreeNode head = new TreeNode(pre[L1]);
if (L1 == R1) {
return head;
}
// 在中序数组中找到根节点
int find = valueIndexMap.get(pre[L1]);
// L1 ... R1
// L2 ..find.. R2
head.left = doBuild(pre, L1 + 1, L1 + find - L2, in, L2, find - 1, valueIndexMap);
head.right = doBuild(pre, L1 + find - L2 + 1, R1, in, find + 1, R2, valueIndexMap);
return head;
}
/**
* 有一棵树，先序结果是pre[L1...R1]，中序结果是in[L2...R2]
*
* @param pre 先序数组
* @param L1 先序数组左下标
* @param R1 先序数组右下标
* @param in 中序数组
* @param L2 中序数组左下标
* @param R2 中序数组右下标
* @return 重建树的根节点
*/
public static TreeNode doBuild1(int[] pre, int L1, int R1, int[] in, int L2, int R2) {
// 范围错过去，就是没有树
if (L1 > R1) {
return null;
}
TreeNode head = new TreeNode(pre[L1]);
if (L1 == R1) {
return head;
}
// 遍历：在中序数组中找到根节点
int find = L2;
while (pre[L1] != in[find]) {
find++;
}
// L1 ... R1
// L2 ..find.. R2
head.left = doBuild1(pre, L1 + 1, L1 + find - L2, in, L2, find - 1);
head.right = doBuild1(pre, L1 + find - L2 + 1, R1, in, find + 1, R2);
return head;
}
}
3.5、二叉树按层遍历并收集节点
给定二叉树的根，返回其节点值的自下而上的层次顺序遍历。 （即，从左到右，从叶到根逐层）。
3.5.1、代码实现
由于要自下而上的层次顺序遍历，所以使用链表，在任何位置插入O(1)
使用队列先进先出，从左到右收集
测试链接：https://leetcode.com/problems/binary-tree-level-order-traversal-ii
public class BinaryTreeLevelOrderTraversalII {
public static List<List<Integer>> levelOrderBottom(TreeNode root) {
List<List<Integer>> res = new LinkedList<>();
if (root == null) {
return res;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
int size = queue.size();
List<Integer> curRes = new LinkedList<>();
for (int i = 0; i < size; i++) {
TreeNode curNode = queue.poll();
curRes.add(curNode.val);
if (curNode.left != null) {
queue.add(curNode.left);
}
if (curNode.right != null) {
queue.add(curNode.right);
}
}
res.add(0, curRes);
}
return res;
}
}
3.6、判断是否是平衡二叉搜索树（AVL树）
平衡二叉搜索树（Balanced Binary Search Tree）是一种结构平衡的[二叉搜索树] ，它是一种每个节点的左右两子[树] 高度差都不超过一的[二叉树] 。它能在O(logn)内完成插入、查找和删除操作，最早被发明的平衡二叉搜索树为[AVL树] 。
3.6.2、代码实现
测试链接：https://leetcode.com/problems/balanced-binary-tree
点击查看代码
public class BalancedBinaryTree {
/**
* balancedFlag: true / false
* 最终返回二叉树是否平衡，递归进行过程中携带其子树是否平衡
* height:
* 最终返回二叉树的高度，递归进行过程中携带每一棵子树的高度
*/
public static class Info {
public boolean balancedFlag;
public int height;
public Info(boolean balancedFlag, int height) {
this.balancedFlag = balancedFlag;
this.height = height;
}
}
public static boolean isBalanced(TreeNode root) {
return process(root).balancedFlag;
}
/**
* 递归判断二叉树是否是平衡二叉搜索树
*
* @param root 二叉树根节点
* @return Info
*/
private static Info process(TreeNode root) {
if (root == null) {
return new Info(true, 0);
}
Info leftInfo = process(root.left);
Info rightInfo = process(root.right);
int height = Math.max(leftInfo.height, rightInfo.height) + 1;
// 左树平衡，与右树平衡，与左右树深度差不超过 1
boolean balancedFlag = leftInfo.balancedFlag && rightInfo.balancedFlag
&& Math.abs(leftInfo.height - rightInfo.height) < 2;
return new Info(balancedFlag, height);
}
public static boolean isBalanced1(TreeNode root) {
if (root == null) {
return true;
}
// 非平衡树
if (height(root) == -1) {
return false;
}
return true;
}
public static int height(TreeNode root) {
if (root == null) {
return 0;
}
int leftHeight = height(root.left);
int rightHight = height(root.right);
if (leftHeight == -1 || rightHight == -1) {
return -1;
}
if (Math.abs(leftHeight - rightHight) > 1) {
return -1;
}
return Math.max(leftHeight, rightHight) + 1;
}
public static void main(String[] args) {
TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.left.left = new TreeNode(5);
// root.left.right = new TreeNode(6);
// root.right.left = new TreeNode(7);
// 实现一
// boolean balanced = isBalanced(root);
// System.out.println(balanced);
// 实现二
int height = height(root);
System.out.println(height);
}
}
3.7、判断是否是二叉搜索树
二叉查找树（Binary Search Tree），（又：二叉搜索树，二叉排序树）它或者是一棵空树，
或者是具有下列性质的二叉树：
- 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
- 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
- 它的左、右子树也分别为二叉排序树。
- 设x是二叉搜索树中的一个结点。如果y是x左子树中的一个结点，那么y.key≤x.key。如果y是x右子树中的一个结点，那么y.key≥x.key。
3.7.2、代码实现
测试地址：https://leetcode.com/problems/validate-binary-search-tree/
点击查看代码
public class IsBinarySearchTree {
public static class Info {
// 是否是二叉搜索树
public boolean BSTFlag;
// 整棵树最小值
public int min;
// 整棵树最大值
public int max;
public Info(boolean BSTFlag, int min, int max) {
this.BSTFlag = BSTFlag;
this.min = min;
this.max = max;
}
}
public boolean isValidBST(TreeNode root) {
return process(root).BSTFlag;
}
public static Info process(TreeNode x) {
if (x == null) {
return null;
}
Info leftInfo = process(x.left);
Info rightInfo = process(x.right);
// 假设当前节点就是最大值、最小值
int min = x.val;
int max = x.val;
if (leftInfo != null) {
min = Math.min(leftInfo.min, min);
max = Math.max(leftInfo.max, max);
}
if (rightInfo != null) {
min = Math.min(rightInfo.min, min);
max = Math.max(rightInfo.max, max);
}
boolean BSTFlag = true;
if (leftInfo != null && !leftInfo.BSTFlag) {
BSTFlag = false;
}
if (rightInfo != null && !rightInfo.BSTFlag) {
BSTFlag = false;
}
boolean leftMaxLessX = leftInfo == null ? true : (leftInfo.max < x.val);
boolean rightMinMoreX = rightInfo == null ? true : (rightInfo.min > x.val);
if (!leftMaxLessX || !rightMinMoreX) {
BSTFlag = false;
}
return new Info(BSTFlag, min, max);
}
}
3.8、能否组成路径和
给定一棵二叉树的根和一个整数 targetSum，如果树有一条从根到叶的路径，
使得沿路径的所有值相加等于 targetSum，则返回 true。 叶子是没有孩子的节点。
3.8.2、代码实现
方式一：从根节点累加到叶子节点，判断和是否等于targetSum
方式二：用targetSum 减去其所经过节点的值，到叶子节点，判断剩余值是否与叶子节点的值相等
测试链接：https://leetcode.com/problems/path-sum
点击查看代码
public class PathSum {
public static boolean isSum = false;
/**
* 能否组成路径和（实现一）
*
* @param root 根节点
* @param targetSum 目标和
* @return true / false,是否有满足条件的路径
*/
public static boolean hasPathSum(TreeNode root, int targetSum) {
if (root == null) {
return false;
}
isSum = false;
process(root, 0, targetSum);
return isSum;
}
/**
* @param cur 当前节点
* @param preSum 当前节点之前的，所有节点的和
* @param targetSum 目标和
*/
private static void process(TreeNode cur, int preSum, int targetSum) {
if (cur.left == null && cur.right == null) {
if (preSum + cur.val == targetSum) {
isSum = true;
}
return;
}
// else cur 为非叶子节点
// 加上当前节点的值往下传
preSum += cur.val;
if (cur.left != null) {
process(cur.left, preSum, targetSum);
}
if (cur.right != null) {
process(cur.right, preSum, targetSum);
}
}
/**
* 能否组成路径和（实现二）
*
* @param root 根节点
* @param targetSum 目标和
* @return true / false,是否有满足条件的路径
*/
public boolean hasPathSum1(TreeNode root, int targetSum) {
if (root == null) {
return false;
}
return process1(root, targetSum);
}
/**
* 用 targetSum 减去其所经过节点的值，到叶子节点时，如果剩余数与之相等，则找到了
* @param cur 当前节点
* @param res 经过节点后的剩余数
* @return true / false,是否有满足条件的路径
*/
private boolean process1(TreeNode cur, int res) {
if (cur.left == null && cur.right == null) {
return cur.val == res;
}
boolean ans = cur.left != null ? process1(cur.left, res - cur.val) : false;
ans |= cur.right != null ? process1(cur.right, res - cur.val) : false;
return ans;
}
3.9、收集达标路径和
给定二叉树的根和整数 targetSum，返回所有根到叶的路径，其中路径中节点值的总和等于 targetSum。
每条路径都应作为节点值列表返回，而不是节点引用。
- 根到叶路径是从根开始到任何叶节点结束的路径。叶子是没有孩子的节点。
3.9.1、代码实现
点击查看代码
public class PathSumII {
public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
List<List<Integer>> ans = new ArrayList<>();
if (root == null) {
return ans;
}
List<Integer> path = new ArrayList<>();
process(root, path, 0, targetSum, ans);
return ans;
}
/**
* 收集达标路径和
*
* @param cur 当前节点
* @param path 到达当前节点已经过的父节点集合
* @param preSum 到达当前节点已经过的父节点累加和
* @param targetSum 目标和
* @param ans 满足条件的路径集合
*/
private void process(TreeNode cur, List<Integer> path, int preSum, int targetSum, List<List<Integer>> ans) {
if (cur.left == null && cur.right == null) {
if (preSum + cur.val == targetSum) {
path.add(cur.val);
// copy 一份放入ans
ans.add(copy(path));
// 返回其父节点时，将自己移除
path.remove(path.size() - 1);
}
return;
}
// else 非叶子节点
path.add(cur.val);
preSum += cur.val;
if (cur.left != null) {
process(cur.left, path, preSum, targetSum, ans);
}
if (cur.right != null) {
process(cur.right, path, preSum, targetSum, ans);
}
// 返回其父节点时，将自己移除
path.remove(path.size() - 1);
}
public List<Integer> copy(List<Integer> path) {
List<Integer> res = new ArrayList<>();
res.addAll(path);
return res;
}
}