树-二叉树
二叉树
概念
二叉树 binary tree 是一种非线性数据结构，代表 父节点 与 子节点 之间的派生关系。二叉树的基本单元是节点，每个节点包含值、左子节点引用和右子节点引用。
/* 二叉树节点类 */
class TreeNode {
int val; // 节点值
TreeNode left; // 左子节点引用
TreeNode right; // 右子节点引用
TreeNode(int x) { val = x; }
}每个节点都有两个引用（指针），分别指向「左子节点 left-child node」和「右子节点 right-child node」，该节点被称为这两个子节点的「父节点 parent node」。当给定一个二叉树的节点时，我们将该节点的左子节点及其以下节点形成的树称为该节点的「左子树 left subtree」，同理可得「右子树 right subtree」。
在二叉树中，除叶节点外，其他所有节点都包含子节点和非空子树。
常用术语
「根节点 root node」：位于二叉树顶层的节点，没有父节点。
「叶节点 leaf node」：没有子节点的节点，其两个指针均指向
None。「边 edge」：连接两个节点的线段，即节点引用（指针）。
节点所在的「层 level」：从顶至底递增，根节点所在层为 1 。
节点的「度 degree」：节点的子节点的数量。在二叉树中，度的取值范围是 0、1、2 。
二叉树的「高度 height」：从根节点到最远叶节点所经过的边的数量。
节点的「深度 depth」：从根节点到该节点所经过的边的数量。
节点的「高度 height」：从距离该节点最远的叶节点到该节点所经过的边的数量。
基本操作
初始化二叉树
// 初始化节点
TreeNode n1 = new TreeNode(1);
TreeNode n2 = new TreeNode(2);
TreeNode n3 = new TreeNode(3);
TreeNode n4 = new TreeNode(4);
TreeNode n5 = new TreeNode(5);
// 构建节点之间的引用（指针）
n1.left = n2;
n1.right = n3;
n2.left = n4;
n2.right = n5;插入与删除节点
通过修改指针操作
TreeNode P = new TreeNode(0);
// 在 n1 -> n2 中间插入节点 P
n1.left = P;
P.left = n2;
// 删除节点 P
n1.left = n2;二叉树类型
完美二叉树【满二叉树】
「完美二叉树 perfect binary tree」所有层的节点都被完全填满。在完美二叉树中，叶节点的度为 0 ，其余所有节点的度都为 2 ；若树的高度为 ℎ ，则节点总数为 2ℎ+1−1 （-1是因为根节点，只有点个节点），呈现标准的指数级关系，反映了自然界中常见的细胞分裂现象。
完全二叉树
「完全二叉树 complete binary tree」只有最底层的节点未被填满，且最底层节点尽量靠左填充。
完满二叉树
「完满二叉树 full binary tree」除了叶节点之外，其余所有节点都有两个子节点。
平衡二叉树
「平衡二叉树 balanced binary tree」中任意节点的左子树和右子树的高度之差的绝对值不超过 1 。
二叉搜索树
前面介绍的树，都没有数值的，而二叉搜索树是有数值的了，二叉搜索树是一个有序树。
若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
它的左、右子树也分别为二叉排序树
下面这两棵树都是搜索树
平衡二叉搜索树
平衡二叉搜索树：又被称为AVL（Adelson-Velsky and Landis）树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
如图：
二叉树的遍历
层次遍历（bfs 广度优先搜索遍历）
「层序遍历 level-order traversal」从顶部到底部逐层遍历二叉树，并在每一层按照从左到右的顺序访问节点。
层序遍历本质上属于「广度优先遍历 breadth-first traversal」，也称「广度优先搜索 breadth-first search, BFS」，它体现了一种“一圈一圈向外扩展”的逐层遍历方式。
层次遍历实现
广度优先遍历通常借助“队列”来实现。队列遵循“先进先出”的规则，而广度优先遍历则遵循“逐层推进”的规则，两者背后的思想是一致的。实现代码如下：
/* 层序遍历 */
List<Integer> levelOrder(TreeNode root) {
// 初始化队列，加入根节点
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
// 初始化一个列表，用于保存遍历序列
List<Integer> list = new ArrayList<>();
while (!queue.isEmpty()) {
TreeNode node = queue.poll(); // 队列出队
list.add(node.val); // 保存节点值
if (node.left != null)
queue.offer(node.left); // 左子节点入队
if (node.right != null)
queue.offer(node.right); // 右子节点入队
}
return list;
}复杂度分析：
时间复杂度为 O(n)：所有节点被访问一次，使用 O(n) 时间，其中 n 为节点数量。
空间复杂度为 O(n)：在最差情况下，即满二叉树时，遍历到最底层之前，队列中最多同时存在 (n+1)/2 个节点，占用 O(n) 空间。
一棵树每层节点的平均数
637. Average of Levels in Binary Tree (Easy)
给定一个非空二叉树的根节点
root, 以数组的形式返回每一层节点的平均值。与实际答案相差10的-5次幂以内的答案可以被接受。示例 1：
输入：root = [3,9,20,null,null,15,7] 输出：[3.00000,14.50000,11.00000] 解释：第 0 层的平均值为 3,第 1 层的平均值为 14.5,第 2 层的平均值为 11 。 因此返回 [3, 14.5, 11] 。
解决方法
public class 一棵树每层节点的平均数 {
public List<Double> averageOfLevels(TreeNode root) {
List<Double> ret = new ArrayList<>();
if (root == null) return ret;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
int cnt = queue.size();
double sum = 0;
for (int i = 0; i < cnt; i++) {
TreeNode node = queue.poll();
sum += node.val;
if (node.left != null) queue.add(node.left);
if (node.right != null) queue.add(node.right);
}
ret.add(sum / cnt);
}
return ret;
}
}得到左下角的节点
513. Find Bottom Left Tree Value (Easy)
给定一个二叉树的 根节点
root，请找出该二叉树的 最底层 最左边 节点的值。假设二叉树中至少有一个节点。
示例 1:
输入: root = [2,1,3] 输出: 1
解决方法：因为要得到左下角的节点，所以队列里我们优先放入右节点
public class 得到左下角的节点 {
public int findBottomLeftValue(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
root = queue.poll();
// 注意是先放入右节点，再放入左节点
if (root.right != null) queue.add(root.right);
if (root.left != null) queue.add(root.left);
}
return root.val;
}
}前中后序遍历（dfs）
1
/ \
2 3
/ \ \
4 5 6层次遍历顺序：[1 2 3 4 5 6]
前序遍历顺序（根左右）：[1 2 4 5 3 6]，第一个节点为根节点
中序遍历顺序（左根右）：[4 2 5 1 3 6]，根节点拆分两棵子树
后序遍历顺序（左右根）：[4 5 2 6 3 1]，最后一个节点为根节点
而前序、中序、后序遍历利用了 DFS 实现。
通过递归的方式实现
前序、中序、后序遍只是在对节点访问的顺序有一点不同，其它都相同。
① 前序
伪代码
void dfs(TreeNode root) {
visit(root);
dfs(root.left);
dfs(root.right);
}代码实现
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
inorder(root, res);
return res;
}
public void inorder(TreeNode root, List<Integer> res) {
if (root == null) {
return;
}
res.add(root.val);
inorder(root.left, res);
inorder(root.right, res);
}② 中序
伪代码
void dfs(TreeNode root) {
dfs(root.left);
visit(root);
dfs(root.right);
}代码实现：
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
inorder(root, res);
return res;
}
public void inorder(TreeNode root, List<Integer> res) {
if (root == null) {
return;
}
inorder(root.left, res);
res.add(root.val);
inorder(root.right, res);
}时间复杂度：O(n)，其中 n 为二叉树节点的个数。二叉树的遍历中每个节点会被访问一次且只会被访问一次。
空间复杂度：O(n)，空间复杂度取决于递归的栈深度，而栈深度在二叉树为一条链的情况下会达到 O(n) 的级别。
③ 后序
伪代码
void dfs(TreeNode root) {
dfs(root.left);
dfs(root.right);
visit(root);
}代码实现
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
inorder(root, res);
return res;
}
public void inorder(TreeNode root, List<Integer> res) {
if (root == null) {
return;
}
inorder(root.left, res);
inorder(root.right, res);
res.add(root.val);
}二叉树的中序遍历*
94. Binary Tree Inorder Traversal (Medium) tags:[算法,字符串解码,阿里,百度,京东,]
给定一个二叉树的根节点
root，返回 它的 中序 遍历 。示例 1：
输入：root = [1,null,2,3] 输出：[1,3,2]
左根右，通过迭代的方式实现
public List<Integer> inorderTraversal_Iteration(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
if (root == null) {
return res;
}
LinkedList<TreeNode> queue = new LinkedList<>();
while (root != null || !queue.isEmpty()) {
// 不断放入左节点,队列中放入节点的顺序的反向即为访问左节点的顺序
while (root != null) {
queue.add(root);
root = root.left;
}
// 最左侧的节点，从最后的节点开始弹出
root = queue.pollLast();
res.add(root.val);
root = root.right;
}
return res;
}时间复杂度：O(n)，其中 n 为二叉树节点的个数。二叉树的遍历中每个节点会被访问一次且只会被访问一次。
空间复杂度：O(n)。空间复杂度取决于栈深度，而栈深度在二叉树为一条链的情况下会达到 O(n) 的级别。
二叉树的前序遍历 *
144. Binary Tree Preorder Traversal (Medium) tags:[算法,二叉树的前序遍历,阿里,快手,]
给你二叉树的根节点
root，返回它节点值的 前序 遍历。示例 1：
输入：root = [1,null,2,3] 输出：[1,2,3]
根左右
public class 二叉树的前序遍历 {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> ret = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
if (node == null) continue;
ret.add(node.val);
stack.push(node.right); // 先右后左，保证左子树先遍历，栈先弹出的是左节点
stack.push(node.left);
}
return ret;
}
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> ret = new ArrayList<>();
if (root == null) return ret;
Stack<TreeNode> stack = new Stack<>();
while (root != null || !stack.isEmpty()) {
while (root != null) {
ret.add(root.val); // 放入左节点支持先加入值
stack.push(root);
root = root.left;
}
root = stack.pop();// 从最底层的左节点弹出（先弹出左节点，第二次循环弹出右节点）
root = root.right;// 继续右节点
}
return ret;
}
}二叉树的后序遍历 *
145. Binary Tree Postorder Traversal (Medium)
左右根
public class 二叉树的后序遍历 {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
if (root == null) {
return res;
}
Deque<TreeNode> stack = new LinkedList<TreeNode>();
TreeNode prev = null;
while (root != null || !stack.isEmpty()) {
while (root != null) {
stack.push(root);
root = root.left;
}
root = stack.pop();
if (root.right == null || root.right == prev) {
res.add(root.val);
prev = root;
root = null;
} else {
stack.push(root);
root = root.right;
}
}
return res;
}
}构建二叉树
从前序与中序遍历序列构造二叉树
题目
给定两个整数数组
preorder和inorder，其中preorder是二叉树的先序遍历，inorder是同一棵树的中序遍历，请构造二叉树并返回其根节点。示例 1:
输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] 输出: [3,9,20,null,null,15,7]
解决方案
对于任意一颗树而言，前序遍历的形式总是
[ 根节点 , [ 左子树的前序遍历结果 ] , [ 右子树的前序遍历结果 ] ]
即根节点总是前序遍历中的第一个节点。而中序遍历的形式总是
[ [ 左子树的中序遍历结果 ] , 根节点 , [ 右子树的中序遍历结果 ] ]
通过这个关系，我们可以通过定位根节点在中序遍历中的坐标，来拆分出左子树和右子树，然后继续递归即可
private Map<Integer, Integer> inorderMap = new HashMap<>();
public TreeNode buildTree(int[] preorder, int[] inorder) {
for (int i = 0; i < inorder.length; i++) {
inorderMap.put(inorder[i], i);
}
return buildTree(preorder, inorder, 0, preorder.length - 1, 0, inorder.length - 1);
}
/**
* @param preorder 前序遍历数组
* @param inorder 中序遍历数组
* @param preorderLeft 前序遍历数组左坐标 （同一个子树）
* @param preorderRight 前序遍历数组右坐标
* @param inorderLeft 中序遍历数组左坐标（同一个子树）
* @param inorderRight 中序遍历数组右坐标
* @return
*/
public TreeNode buildTree(int[] preorder, int[] inorder, int preorderLeft, int preorderRight, int inorderLeft, int inorderRight) {
if (preorderLeft > preorderRight) {
return null;
}
// 创建跟节点
TreeNode root = new TreeNode(preorder[preorderLeft]);
// 确认子树跟节点在中序遍历的坐标
Integer rootIndex = inorderMap.get(preorder[preorderLeft]);
// 左子树大小
int leftSize = rootIndex - inorderLeft;
root.left = buildTree(preorder, inorder,
preorderLeft + 1, preorderLeft + leftSize,
inorderLeft, rootIndex - 1);
root.right = buildTree(preorder, inorder,
preorderLeft + leftSize + 1, preorderRight,
rootIndex + 1, inorderRight);
return root;
}从中序与后序遍历序列构造二叉树
题目
给定两个整数数组
inorder和postorder，其中inorder是二叉树的中序遍历，postorder是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。示例 1:
输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3] 输出：[3,9,20,null,null,15,7]
解决方案
对于任意一颗树而言，后序遍历的形式总是
[ [ 左子树的前序遍历结果 ] , [ 右子树的前序遍历结果 ] , 根节点 ]
即根节点总是前序遍历中的第一个节点。而中序遍历的形式总是
[ [ 左子树的中序遍历结果 ] , 根节点 , [ 右子树的中序遍历结果 ] ]
通过这个关系，我们可以通过定位根节点在中序遍历中的坐标，来拆分出左子树和右子树，然后继续递归即可
private Map<Integer, Integer> inorderMap = new HashMap<>();
public TreeNode buildTree(int[] inorder, int[] postorder) {
for (int i = 0; i < inorder.length; i++) {
inorderMap.put(inorder[i], i);
}
return buildTree(inorder, postorder, 0, inorder.length - 1, 0, postorder.length - 1);
}
/**
* @param inorder 中序遍历数组
* @param postorder 后序遍历数组
* @param inorderLeft 中序遍历数组左坐标（同一个子树）
* @param inorderRight 中序遍历数组右坐标
* @param postorderLeft 后序遍历数组左坐标 （同一个子树）
* @param postorderRight 后序遍历数组右坐标
* @return
*/
public TreeNode buildTree(int[] inorder, int[] postorder, int inorderLeft, int inorderRight, int postorderLeft, int postorderRight) {
if (inorderLeft > inorderRight) {
return null;
}
// 创建跟节点
TreeNode root = new TreeNode(postorder[postorderRight]);
// 确认子树跟节点在中序遍历的坐标
Integer rootIndex = inorderMap.get(postorder[postorderRight]);
// 左子树大小
int leftSize = rootIndex - inorderLeft;
root.left = buildTree(inorder, postorder,
inorderLeft, rootIndex - 1,
postorderLeft, postorderLeft + leftSize - 1);
root.right = buildTree(inorder, postorder,
rootIndex + 1, inorderRight,
postorderLeft + leftSize, postorderRight - 1);
return root;
}二叉树的高度
通过递归的方式获取二叉树的高度
public static int getHight(TreeNode root) {
if (root == null) {
return 0;
}
return 1 + Math.max(getHight(root.left), getHight(root.right));
}