有两种通用的遍历树的策略：
- 深度优先搜索（DFS）（栈）
- 在这个策略中，我们采用深度作为优先级，以便从跟开始一直到达某个确定的叶子，然后再返回根到达另一个分支。
- 深度优先搜索策略又可以根据根节点、左孩子和右孩子的相对顺序被细分为先序遍历，中序遍历和后序遍历。
- 广度优先搜索（BFS）（队列）
- 我们按照高度顺序一层一层的访问整棵树，高层次的节点将会比低层次的节点先被访问到。
1
/ \
2 3
/ \ \
4 5 6
- 前序遍历：根节点->左子树->右子树 [1 2 4 5 3 6]
- 中序遍历：左子树->根节点->右子树 [4 2 5 1 3 6]
- 后序遍历：左子树->右子树->根节点 [4 5 2 6 3 1]
- 层序遍历：[1 2 3 4 5 6]
题目出处
- 前序遍历
- 中序遍历
- 后序遍历
- 层序遍历
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
1 前序遍历
1.1 递归解法
“自顶向下” 的解决方案
在每个递归层级，首先访问节点来计算一些值，并在递归调用函数时将这些值传递到子节点。
1. return specific value for null node
2. update the answer if needed // answer <-- params
3. left_ans = top_down(root.left, left_params) // left_params <-- root.val, params
4. right_ans = top_down(root.right, right_params) // right_params <-- root.val, params
5. return the answer if needed // answer <-- left_ans, right_ans
- 如果二叉树为空，空操作
- 如果二叉树不为空，访问根节点，前序遍历左子树，前序遍历右子树
class Solution {
public static void preorderTraversalRec(TreeNode root) {
if (root == null) {
return;
}
System.out.print(root.val + " ");
preorderTraversalRec(root.left);
preorderTraversalRec(root.right);
}
}
1.2 迭代解法
用一个辅助栈，从根节点开始，每次迭代弹出当前栈顶元素，并将其孩子节点压入栈中，先压右孩子再压左孩子。
- 时间复杂度：访问每个节点恰好一次，时间复杂度为 O(N)。
- 空间复杂度：取决于树的结构，最坏情况存储整棵树，因此空间复杂度是 O(N)。
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (null == root) {
return result;
}
Deque<TreeNode> stack = new ArrayDeque<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
result.add(node.val);
//FILO, push right first,can get left earlier
if (null != node.right) {
stack.push(node.right);
}
if (null != node.left) {
stack.push(node.left);
}
}
return result;
}
}
1.3 相关试题
1）判断两棵二叉树是否相同
递归解法
- 如果两棵二叉树都为空，返回真
- 如果两棵二叉树一棵为空，另一棵不为空，返回假
- 如果两棵二叉树都不为空，如果对应的左子树和右子树都同构返回真，其他返回假
迭代解法
前序遍历，对每个节点进行比较
2）自顶向下的最大深度
class Solution {
private int answer; // don't forget to initialize answer before call maximum_depth
private void maximum_depth(TreeNode root, int depth) {
if (root == null) {
return;
}
if (root.left == null && root.right == null) {
answer = Math.max(answer, depth);
}
maximum_depth(root.left, depth + 1);
maximum_depth(root.right, depth + 1);
}
}
2 中序遍历
2.1 递归解法
中序遍历递归解法
- 如果二叉树为空，空操作。
- 如果二叉树不为空，中序遍历左子树，访问根节点，中序遍历右子树
class Solution {
public static void inorderTraversalRec(TreeNode root) {
if (root == null) {
return;
}
inorderTraversalRec(root.left);
System.out.print(root.val + " ");
inorderTraversalRec(root.right);
}
}
2.2 迭代解法
用栈先把根节点的所有左孩子都添加到栈内，然后输出栈顶元素，再处理栈顶元素的右子树
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
if (null == root) {
return list;
}
Deque<TreeNode> stack = new ArrayDeque<>();
while (true) {
//1. push all left nodes into stack
while (null != root) {
stack.push(root);
root = root.left;
}
//2. get previous pushed node to continue
//2.1 if empty, means finished
if (stack.isEmpty()) {
break;
}
//2.2 get one
TreeNode node = stack.pop();
//3. handle (left)middle
list.add(node.val);
//4. handle right
root = node.right;
}
return list;
}
}
3 后序遍历
3.1 递归解法
“自底向上” 的解决方案
在每个递归层次上，我们首先对所有子节点递归地调用函数，然后根据返回值和根节点本身的值得到答案。
1. return specific value for null node
2. left_ans = bottom_up(root.left) // call function recursively for left child
3. right_ans = bottom_up(root.right) // call function recursively for right child
4. return answers // answer <-- left_ans, right_ans, root.val
- 如果二叉树为空，空操作
- 如果二叉树不为空，后序遍历左子树，后序遍历右子树，访问根节点
class Solution {
public static void postorderTraversalRec(TreeNode root) {
if (root == null) {
return;
}
postorderTraversalRec(root.left);
postorderTraversalRec(root.right);
System.out.print(root.val + " ");
}
}
3.2 迭代解法
后序遍历跟中序遍历很像，先遍历左边，判断中点时，先判断有没有右节点，有的话要先处理右边。
处理完右边会回到中点，中点还是有右节点，为了不陷入循环，需要记录下右节点是否处理过。
因为每个中点只关心一个右节点，并且这个右节点pop之后下一个pop的一定是对应的中点，所以只需要一个额外变量记录处理过的右节点。
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (null == root) {
return result;
}
Deque<TreeNode> stack = new ArrayDeque<>();
TreeNode handledRight = null;
while (true) {
//1. push all left nodes into stack
while (null != root) {
stack.push(root);
root = root.left;
}
//2. get previous pushed node to continue
//2.1 if empty, means finished
if (stack.isEmpty()) {
break;
}
//2.2 get one
TreeNode node = stack.pop();
//3.1 if has right, current node is a middle node
if (null != node.right && node.right != handledRight) {
// if right hasn't been handled, push current middle note back to stack
stack.push(node);
// start to handle right
root = node.right;
} else {
//3.2 if doesn't has right, or right has been handled, can handle middle node
result.add(node.val);
handledRight = node;
}
}
return result;
}
}
`
3.3 相关试题
1）自底向上的最大深度
class Solution {
public int maximum_depth(TreeNode root) {
if (root == null) {
return 0; // return 0 for null node
}
int left_depth = maximum_depth(root.left);
int right_depth = maximum_depth(root.right);
return Math.max(left_depth, right_depth) + 1; // return depth of the subtree rooted at root
}
}
4 层序遍历
4.1 递归解法
很少有人会用递归去做 level traversal，基本思想是用一个大的 ArrayList，里面包含了每一层的 ArrayList。大的 ArrayList 的 size 和 level 有关系
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> levels = new ArrayList<>();
if (null == root) {
return levels;
}
dfs(root, 0, levels);
return levels;
}
private static void dfs(TreeNode node, int level, List<List<Integer>> levels) {
// 添加一个新的 ArrayList 表示新的一层
if (level >= levels.size()) {
levels.add(new ArrayList<Integer>());
}
// 把节点添加到当前这层的 ArrayList 里
levels.get(level).add(node.val);
// 递归处理下一层的左子树和右子树
if (null != node.left) {
dfs(node.left, level + 1, levels);
}
if (null != node.right) {
dfs(node.right, level + 1, levels);
}
}
}
4.2 迭代解法
相当于广度优先搜索，使用队列实现。队列初始化，将根节点压入队列。当队列不为空，进行如下操作： 弹出一个节点 ，访问，若左子节点或右子节点不为空，将其压入队列
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> levels = new ArrayList<>();
if (null == root) {
return levels;
}
Deque<TreeNode> queue = new ArrayDeque<>();
queue.addLast(root);
//each loop, handle one level
while (!queue.isEmpty()) {
List<Integer> thisLevel = new ArrayList<>();
//nodes in queue now if from one level
int thisLevelSize = queue.size();
while (thisLevelSize-- > 0) {
//fetch this level's node
TreeNode node = queue.removeFirst();
thisLevel.add(node.val);
//add next level node into queue
if (null != node.left) {
queue.addLast(node.left);
}
if (null != node.right) {
queue.addLast(node.right);
}
}
levels.add(thisLevel);
}
return levels;
}
}
4.3 相关试题
1）自底向上的层次遍历
在层次遍历的基础上，使返回的列表是倒序就行
class Solution {
public List<List<Integer>> levelOrderBottom(TreeNode root) {
LinkedList<List<Integer>> result = new LinkedList<>();
if (null == root) {
return result;
}
ArrayDeque<TreeNode> queue = new ArrayDeque<>();
int level = 0;
queue.addLast(root);
while (!queue.isEmpty()) {
result.addFirst(new ArrayList<>());
int levelSize = queue.size();
for (int i = 0; i < levelSize; i++) {
TreeNode node = queue.removeFirst();
result.get(0).add(node.val);
if (null != node.left) {
queue.addLast(node.left);
}
if (null != node.right) {
queue.addLast(node.right);
}
}
levelSize++;
}
return result;
}
}
2）一棵树每层节点的平均数
问题：给定一个非空二叉树, 返回一个由每层节点平均值组成的数组.
思路：层序遍历，计算每层的平均值
class Solution {
public List<Double> averageOfLevels(TreeNode root) {
List<Double> result = new ArrayList<>();
if (null == root) {
return result;
}
ArrayDeque<TreeNode> queue = new ArrayDeque<>();
queue.addLast(root);
while (!queue.isEmpty()) {
int count = queue.size();
double sum = 0;
for (int i = 0; i < count; ++i) {
TreeNode node = queue.removeFirst();
sum += node.val;
if (null != node.left) {
queue.addLast(node.left);
}
if (null != node.right) {
queue.addLast(node.right);
}
}
result.add(sum / count);
}
return result;
}
}
3）得到左下角的节点
问题：给定一个二叉树，在树的最后一行找到最左边的值。
思路：层序遍历，从右到左，遍历的最后一个节点就是左下角的节点
class Solution {
public int findBottomLeftValue(TreeNode root) {
Queue<TreeNode> queue = new ArrayDeque<>();
queue.add(root);
while (!queue.isEmpty()) {
root = queue.poll();
if (null != root.right) {
queue.add(root.right);
}
if (null != root.left) {
queue.add(root.left);
}
}
return root.val;
}
}
4）求二叉树中的节点个数
- 递归：
- 如果二叉树为空，节点个数为 0；
- 如果二叉树不为空，二叉树节点个数 = 左子树节点个数 + 右子树节点个数 + 1
- 迭代：同层序遍历，每次往队列里加节点的时候计数加一
5）二叉树的最大深度
递归解法
- 如果二叉树为空，二叉树的深度为 0
- 如果二叉树不为空，二叉树的深度 = max(左子树深度， 右子树深度) + 1
class Solution {
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}
}
迭代解法
层序遍历，每层加一
6）求二叉树第 K 层的节点个数
递归解法
- 如果二叉树为空或者 k < 1 返回 0
- 如果二叉树不为空并且 k== 1，返回 1
- 如果二叉树不为空且 k > 1，返回 root 左子树中 k-1 层的节点个数与 root 右子树 k-1 层节点个数之和
class Solution {
public static int getNodeNumKthLevelRec(TreeNode root, int k) {
if (root == null || k < 1) {
return 0;
}
if (k == 1) {
return 1;
}
int numLeft = getNodeNumKthLevelRec(root.left, k - 1);
int numRight = getNodeNumKthLevelRec(root.right, k - 1);
return numLeft + numRight;
}
}
迭代解法
层序遍历，到第 k 层时计数
7）求二叉树中叶子节点的个数
递归解法
- 若当前节点为空，返回 0
- 当前节点为叶子节点，返回 1
- 否则返回左右子树的叶子节点之和
class Solution {
public int getNodeNumLeafRec(TreeNode root) {
if (root == null) {
return 0;
}
if (root.left == null && root.right == null) {
return 1;
}
return getNodeNumLeafRec(root.left) + getNodeNumLeafRec(root.right);
}
}
迭代解法
层序遍历，如果当前节点没有左右子树，则是叶子节点，计数加一
5 其它
自顶向下
101. 对称二叉树
递归
- 如果一个树的左子树与右子树镜像对称，那么这个树是对称的。
- 如果同时满足下面的条件，两个树互为镜像：
- 它们的两个根结点具有相同的值
- 每个树的右子树都与另一个树的左子树镜像对称
class Solution {
public boolean isSymmetric(TreeNode root) {
return isSymmetric(root, root);
}
private boolean isSymmetric(TreeNode left, TreeNode right) {
if (left == null && right == null) {
return true;
} else if (left == null || right == null) {
return false;
} else if (left.val != right.val) {
return false;
} else {
//每个树的右子树都与另一个树的左子树镜像对称
return isSymmetric(left.left, right.right) && isSymmetric(right.left, left.right);
}
}
}
迭代
引入一个队列，把递归改写成迭代。
- 将应该镜像的两个点连续入队（两个结点的左右子结点按相反的顺序插入队列中）
- 每次提取两个结点并比较它们的值，然后插入两个结点的左右子结点
- 当队列为空时，或者我们检测到树不对称（即从队列中取出两个不相等的连续结点）时，该算法结束
class Solution {
public boolean isSymmetric(TreeNode root) {
return isSymmetric(root, root);
}
public boolean isSymmetric(TreeNode left, TreeNode right) {
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(left);
queue.offer(right);
while(!queue.isEmpty()){
TreeNode newLeft = queue.poll();
TreeNode newRight = queue.poll();
if(newLeft == null && newRight == null){
continue;
}
if(newLeft == null || newRight == null){
return false;
}
if(newLeft.val != newRight.val){
return false;
}
queue.offer(newLeft.left);
queue.offer(newRight.right);
queue.offer(newLeft.right);
queue.offer(newRight.left);
}
return true;
}
}