面试算法：二叉树
程序员文章站
2022-06-28 17:42:58
文章目录一、什么是深度优先搜索？二、深度优先搜索模版三、三种宽度优先搜索题型1. 连通块2. 分层遍历3. 拓扑排序四、题目一、什么是深度优先搜索？深度优先搜索是图的一种遍历策略，它的思想是从一个点开始，沿着一条分支遍历到底，当无法继续遍历的时候，向上一次次回溯，每次回溯选择另一条分支遍历到低。二、深度优先搜索模版三、三种宽度优先搜索题型1. 连通块通过一个点，找到所有图中与之连通的点。 连通块问题都可以用宽度有限搜索模版解决，但是对于矩阵中的连通块问题，需要用到坐标变换数组，有一个更细...
文章目录
一、什么是二叉树？
二叉树是一棵空树，或者是一棵由一个根节点和两棵互不相交的，分别称作根的左子树和右子树组成的非空树；左子树和右子树又同样都是二叉树
二、遍历
1. Depth First Traversals
-
先序遍历 Pre-order
- Visit the root.
- Traverse the left subtree, i.e., call Preorder(left-subtree)
- Traverse the right subtree, i.e., call Preorder(right-subtree)
-
中序遍历 In-order
- Traverse the left subtree, i.e., call Inorder(left-subtree)
- Visit the root.
- Traverse the right subtree, i.e., call Inorder(right-subtree)
-
后序遍历 Post-order
- Traverse the left subtree, i.e., call Postorder(left-subtree)
- Traverse the right subtree, i.e., call Postorder(right-subtree)
- Visit the root.
2. Breadth First or Level Order Traversal
三、三种二叉树题型
1. 求值
从二叉树中求子数的值（depth, average, sum, lowest common ancestor, path)。
使用分治法，把左子树的值和右子树的值通过递归，传递给根节点。
有两种传递的方式：
- Return Value / Class (新建一个class来return多个值）
class ResultType {
...;
...;
public ResultType(...) {
...
}
}
private ResultType helper(TreeNode root) {
if (root == null) {
return new ResultType(...);
}
ResultType left = helper(root.left);
ResultType right = helper(root.right);
if (left...right) {
return new ResultType(...);
}
if (left...right) {
return new ResultType(...);
}
return new ResultType(...);
}
- Parameter （通过parameter把值传递给caller）
private void foo(TreeNode node, List<> list) {
if (node.left == null && node.right == null) {
list.add(...);
return;
}
if (node.left != null) {
foo(node.left, list);
}
if (node.right != null) {
foo(node.right, , list);
}
}
2. 结构变换
一般涉及到二叉树翻转，变成list或者string。
没有固定模版，根据情况使用BFS/DFS来解决。
3. 搜索
只需要记一个模版即可：
binary search tree iterator
先从根结点遍历二叉树搜索出一个起始点，然后用binary search tree iterator来搜就行。
四、题目
https://blog.csdn.net/Kejonho/article/details/109759581
本文地址：https://blog.csdn.net/Kejonho/article/details/111306097