遍历递归
递归的步骤主要分为三步
- 确定递归函数的参数和返回值：将根节点以及返回的数组传入，而不需要返回值
- 确定终止条件：当根节点为null时，结束递归
- 单次递归逻辑：以前序遍历为例：先将中间节点的值加入数组，然后将左右节点传入递归函数
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<Integer>();
preorder(root, result);
return result;
}
public void preorder(TreeNode root, List<Integer> result) {
if (root == null) {
return;
}
result.add(root.val);
preorder(root.left, result);
preorder(root.right, result);
}
}
迭代遍历
迭代遍历使用栈的方式实现，是一种深度优先搜索的方法，其中前序遍历和后续遍历比较类似，而中序遍历是另一种处理方法
- 前序遍历
前序遍历要求结果是中左右，但由于栈是后进先出，所以加入栈的顺序是中右左，每次都是中间的先加入
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
if (root == null) {
return list;
}
stack.push(root);
// 一次pop，两次push
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
list.add(node.val);
if (node.right != null) {
stack.push(node.right);
}
if (node.left != null) {
stack.push(node.left);
}
}
return list;
}
}
- 后序遍历
后续遍历要求是左右中，加入栈的顺序应该是中左右，取出的顺序是中右左，然后反转数组即可
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
if (root == null) {
return list;
}
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
list.add(node.val);
if (node.left != null) {
stack.push(node.left);
}
if (node.right != null) {
stack.push(node.right);
}
}
Collections.reverse(list);
return list;
}
}
- 中序遍历
先将所有的左节点加入栈中，然后再处理右节点
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
if (root == null) {
return list;
}
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
while (cur != null || !stack.isEmpty()) {
// 先将所有的左节点加入栈中
if (cur != null) {
stack.push(cur);
cur = cur.left;
} else {
// 然后处理右节点
cur = stack.pop();
list.add(cur.val);
cur = cur.right;
}
}
return list;
}
}
层序遍历
102. 二叉树的层序遍历
层序遍历返回的是一个二维数组，记录每层节点的数值，需要使用一个辅助队列，记录每层节点的个数，每次取元素时，都将左右节点放入队列，知道该层元素取完，进入下一层
层序遍历是一种广度优先搜索方法（BFS）
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
if (root == null) {
return result;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
List<Integer> itemList = new ArrayList<>();
int len = queue.size();
// 取出一个，加入两个
while (len > 0) {
TreeNode tree = queue.poll();
itemList.add(tree.val);
if (tree.left != null) {
queue.offer(tree.left);
}
if (tree.right != null) {
queue.offer(tree.right);
}
len--;
}
result.add(itemList);
}
return result;
}
}
