algorithm-pattern-java
搜索文档…
⌃K

二叉树

二叉树遍历

先访问根节点,再前序遍历左子树,再前序遍历右子树
先中序遍历左子树,再访问根节点,再中序遍历右子树
先后序遍历左子树,再后序遍历右子树,再访问根节点
注意点
  • 以根访问顺序决定是什么遍历
  • 左子树都比右子树优先遍历

递归遍历

// 递归遍历写法,以前序遍历为例
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new LinkedList<>();
traverse(root, result);
return result;
}
public void traverse(TreeNode p, List<Integer> result) {
if (p == null) {
return;
}
// 其他遍历调整这里的语句顺序即可
result.add(p.val);
traverse(p.left, result);
traverse(p.right, result);
}

前序非递归

// 通过非递归遍历
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
TreeNode p = root;
while (p != null || ! stack.isEmpty()) {
while (p != null) {
// 前序遍历,所以先保存结果
result.add(p.val);
stack.push(p);
p = p.left;
}
// pop出栈顶元素
if (! stack.isEmpty()) {
p = stack.pop();
p = p.right;
}
}
return result;
}

中序非递归

// 思路:通过stack 保存已经访问的元素,用于原路返回
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new LinkedList<>();
Stack<TreeNode> stack = new Stack<>();
TreeNode p = root;
while (p != null || ! stack.isEmpty()) {
if (p != null) {
stack.push(p);
p = p.left;
} else {
TreeNode node = stack.pop();
result.add(node.val);
p = node.right;
}
}
return result;
}

后序非递归

public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode p = root;
// 通过lastVisit标识右子节点是否已经弹出
TreeNode lastVisit = root;
while (p != null || !stack.isEmpty()) {
while (p != null) {
stack.push(p);
p = p.left;
}
//查看当前栈顶元素
p = stack.peek();
//如果其右子树也为空,或者右子树已经访问,则可以访问
if (p.right == null || p.right == lastVisit) {
result.add(p.val);
stack.pop();
// 标记当前这个节点已经弹出过
lastVisit = p;
p = null;
} else {
//否则继续遍历右子树
p = p.right;
}
}
return result;
}
注意点
  • 核心就是:根节点必须在右节点弹出之后,再弹出

DFS 深度搜索

给定一个二叉树,返回所有从根节点到叶子节点的路径。
public List<String> binaryTreePaths(TreeNode root) {
StringBuilder path = new StringBuilder();
List<String> paths = new LinkedList<>();
dfs(root, path, paths);
return paths;
}
public void dfs(TreeNode p, StringBuilder path, List<String> paths) {
if (p == null) {
return;
}
path.append(p.val);
// 当前节点是叶子节点
if (p.left == null && p.right == null) {
// 把路径加入结果
paths.add(path.toString());
} else {
path.append("->");
// 这里需要复制创建新的StringBuilder对象
dfs(p.left, new StringBuilder(path), paths);
dfs(p.right, new StringBuilder(path), paths);
}
}

BFS 层次遍历

public List<Integer> levelOrder(TreeNode root) {
List<Integer> result = new LinkedList<>();
if (root == null) {
return result;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode p = queue.pop();
result.add(p);
if (p.left != null) {
queue.add(p.left);
numList.add(p.left.val);
}
if (p.right != null) {
queue.add(p.right);
numList.add(p.right.val);
}
}
return result
}

二叉树分治

先分别处理局部,再合并结果
分治法模板
  • 递归返回条件
  • 分段处理
  • 合并结果
public ResultType traversal(TreeNode root) {
// null or leaf
if (root == null) {
// do something and return
}
// Divide
ResultType left = traversal(root.Left)
ResultType right = traversal(root.Right)
// Conquer
ResultType result = Merge from left and right
return result
}

典型示例

给定一个二叉树,判断其是否是一个有效的二叉搜索树。
public boolean isValidBST(TreeNode root) {
return divideAndConquer(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
private boolean divideAndConquer(TreeNode p, long min, long max) {
if (p == null) return true;
// 返回条件
if (p.val <= min || max <= p.val) {
return false;
}
// 分治(Divide)
boolean left = divideAndConquer(p.left, min, p.val);
boolean right = divideAndConquer(p.right, p.val, max);
// 合并结果(Conquer)
return left && right;
}
注意点:
DFS 深度搜索(从上到下) 和分治法区别:前者一般将最终结果通过参数传入,后者一般递归返回结果最后合并

常见题目

二叉树的最大深度

给定一个二叉树,找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
思路:分治法
public int maxDepth(TreeNode root) {
// 返回条件处理
if (root == null) {
return 0;
}
// divide:分左右子树分别计算
// conquer:合并左右子树结果,即取二者中的最大值加一
return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}

平衡二叉树

给定一个二叉树,判断它是否是高度平衡的二叉树。
思路:分治法,左边平衡 && 右边平衡 && 左右两边高度 <= 1,因为需要返回是否平衡及高度,要么返回两个数据,要么合并两个数据,所以用-1 表示不平衡,>0 表示树高度(二义性:一个变量有两种含义)。
public boolean isBalanced(TreeNode root) {
return maxDepth(root) >= 0;
}
private int maxDepth(TreeNode p) {
if (p == null) {
return 0;
}
int left = maxDepth(p.left);
int right = maxDepth(p.right);
if (left < 0 || right < 0 || Math.abs(left - right) > 1) {
return -1;
} else {
return Math.max(left, right) + 1;
}
}
注意
一般工程中,结果通过两个变量来返回,不建议用一个变量表示两种含义

二叉树中的最大路径和

路径 被定义为一条从树中任意节点出发,沿父节点-子节点连接,达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点,且不一定经过根节点。
路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 root ,返回其 最大路径和
思路:分治法,分为三种情况:左子树最大路径和最大,右子树最大路径和最大,左右子树最大加根节点最大,需要保存两个变量:一个保存子树最大路径和,一个保存左右加根节点和,然后比较这个两个变量选择最大值即可
public int maxPathSum(TreeNode root) {
return maxSum(root)[1];
}
// 返回的数组意义:int[0]表示单边最大值,int[1]表示所有情况的最大值(单边或者两个单边+根的值)
private int[] maxSum(TreeNode p) {
// check
if (p == null) {
return new int[]{0, Integer.MIN_VALUE};
}
// Divide
int[] left = maxSum(p.left);
int[] right = maxSum(p.right);
int singleSum, bothSum;
// Conquer
// 求单边最大值
if (left[0] > right[0]) {
singleSum = Math.max(left[0] + p.val, 0);
} else {
singleSum = Math.max(right[0] + p.val, 0);
}
// 求所有情况(两个子树的所有情况、两个单边最大值与根之和)的最大值
bothSum = Math.max(left[1], right[1]);
bothSum = Math.max(bothSum, left[0] + right[0] + p.val);
return new int[]{singleSum, bothSum};
}

二叉树的最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
思路:分治法,有左子树的公共祖先或者有右子树的公共祖先,就返回子树的祖先,否则返回根节点
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
// check
if (root == null) {
return null;
}
// 相等 直接返回root节点即可
if (root == p || root == q) {
return root;
}
// Divide
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
// Conquer
// 左右两边都不为空,则根节点为祖先
if (left != null && right != null) {
return root;
} else if (left != null) {
return left;
} else {
return right;
}
}

BFS 应用

常见题目

二叉树的层序遍历

给你一个二叉树,请你返回其按 层序遍历 得到的节点值。 (即逐层地,从左到右访问所有节点)
思路:用一个队列记录一层的元素,然后扫描这一层元素添加下一层元素到队列(一个数进去出来一次,所以复杂度 O(logN))
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result = new LinkedList<>();
if (root == null) {
return result;
}
LinkedList<TreeNode> queue = new LinkedList<>();
LinkedList<Integer> numList = new LinkedList<>();
queue.add(root);
numList.add(root.val);
while (! queue.isEmpty()) {
// 保存这一层的元素
result.add(numList);
numList = new LinkedList<>();
// 记录当前层有多少元素(遍历当前层,再添加下一层)
int len = queue.size();
for (int i = 0; i < len; i++) {
// 出队列
TreeNode p = queue.pop();
if (p.left != null) {
queue.add(p.left);
numList.add(p.left.val);
}
if (p.right != null) {
queue.add(p.right);
numList.add(p.right.val);
}
}
}
return result;
}

二叉树的层序遍历 II

给定一个二叉树,返回其节点值自底向上的层次遍历。 (即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历)
思路:在层级遍历的基础上,翻转一下结果即可,在往result内添加元素之前使用Collections.reverse方法翻转列表。

二叉树的锯齿形层序遍历

给定一个二叉树,返回其节点值的锯齿形层次遍历。Z 字形遍历
思路:在层级遍历的基础上,判断这一层是否需要翻转,在往result内添加元素之前加入以下代码:
if (result.size() % 2 != 0) {
Collections.reverse(numList);
}

二叉搜索树应用

常见题目

二叉搜索树中的插入操作

给定二叉搜索树(BST)的根节点和要插入树中的值,将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。
思路:找到最后一个叶子节点满足插入条件即可
// DFS查找插入位置
public TreeNode insertIntoBST(TreeNode root, int val) {
if (root == null) {
return new TreeNode(val);
}
if (root.val > val) {
root.left = insertIntoBST(root.left, val);
} else {
root.right = insertIntoBST(root.right, val);
}
return root;
}

总结

  • 掌握二叉树递归与非递归遍历
  • 理解 DFS 前序遍历与分治法
  • 理解 BFS 层次遍历