1. 题目
https://leetcode-cn.com/problems/binary-tree-inorder-traversal/https://leetcode-cn.com/problems/binary-tree-preorder-traversal/https://leetcode-cn.com/problems/n-ary-tree-preorder-traversal/https://leetcode-cn.com/problems/n-ary-tree-postorder-traversal/https://leetcode-cn.com/problems/n-ary-tree-level-order-traversal/
2. 题解
2.1 二叉树的中序遍历#94（简单）
https://leetcode-cn.com/problems/binary-tree-inorder-traversal/
public List<Integer> inorderTraversal(TreeNode root) {
//法一:递归.时间复杂度O(n),空间复杂度O(n)
List<Integer> ans = new ArrayList<>();
if (root == null) {
return ans;
}
dfs(root, ans);
return ans;
}
private void dfs(TreeNode node, List<Integer> list) {
if (node == null) {
return;
}
dfs(node.left, list);
list.add(node.val);
dfs(node.right, list);
}
public List<Integer> inorderTraversal(TreeNode root) {
//法二:迭代.时间复杂度O(n),空间复杂度O(n)
//递归隐式的维护了一个栈，迭代就需要自己维护一个栈。
//遍历左子树的时候把左节点入栈，左节点为空时出栈
//出栈的节点加入list，然后遍历右子树
List<Integer> ans = new ArrayList<>();
Deque<TreeNode> stack = new LinkedList<>();
while (root != null || !stack.isEmpty()) {
while (root != null) {
stack.push(root);
root = root.left;
}
root = stack.pop();
ans.add(root.val);
root = root.right;
}
return ans;
}
//直接抄官方题解，要多看几遍官方题解才能理解
public List<Integer> inorderTraversal(TreeNode root) {
//法三:Morris遍历算法.时间复杂度O(n),空间复杂度O(1)
List<Integer> ans = new ArrayList<>();
TreeNode predecessor = null;
while (root != null) {
if (root.left != null) {
//predecessor节点就是当前root节点向左走一步，然后一直向右走到无法走为止
predecessor = root.left;
while (predecessor.right != null && predecessor.right != root) {
predecessor = predecessor.right;
}
//让predecessor的右指针指向root，继续遍历左子树
if (predecessor.right == null) {
predecessor.right = root;
root = root.left;
}
//说明左子树已经访问完了，我们需要断开连接
else {
ans.add(root.val);
predecessor.right = null;
root = root.right;
}
}
//如果没有左孩子，则直接访问右孩子
else {
ans.add(root.val);
root = root.right;
}
}
return ans;
}
2.2 二叉树的前序遍历#144（简单）
https://leetcode-cn.com/problems/binary-tree-preorder-traversal/
public List<Integer> preorderTraversal(TreeNode root) {
//法一:递归.时间复杂度O(n),空间复杂度O(n)
List<Integer> ans = new ArrayList<>();
if (root == null) {
return ans;
}
preOrder(root, ans);
return ans;
}
private void preOrder(TreeNode node, List<Integer> list) {
if (node == null) {
return;
}
list.add(node.val);
preOrder(node.left, list);
preOrder(node.right, list);
}
public List<Integer> preorderTraversal(TreeNode root) {
//法二:迭代.时间复杂度O(n),空间复杂度O(n)
List<Integer> ans = new ArrayList<>();
if (root == null) {
return ans;
}
Deque<TreeNode> stack = new LinkedList<>();
TreeNode node = root;
while (node != null || !stack.isEmpty()) {
while (node != null) {
ans.add(node.val);
stack.push(node);
node = node.left;
}
node = stack.pop();
node = node.right;
}
return ans;
}
//方法三：Morris遍历。时间复杂度O(n),空间复杂度O(1)。直接抄官方题解
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
if (root == null) {
return res;
}
TreeNode p1 = root, p2 = null;
while (p1 != null) {
p2 = p1.left;
if (p2 != null) {
while (p2.right != null && p2.right != p1) {
p2 = p2.right;
}
if (p2.right == null) {
res.add(p1.val);
p2.right = p1;
p1 = p1.left;
continue;
} else {
p2.right = null;
}
} else {
res.add(p1.val);
}
p1 = p1.right;
}
return res;
}
注：关于下面的迭代写法，官方题解的评论区有说不是真的前序/后序遍历的，有争议。
2.3 N叉树的前序遍历#589（简单）
https://leetcode-cn.com/problems/n-ary-tree-preorder-traversal/
class Solution {
public List<Integer> preorder(Node root) {
//法一:递归.时间复杂度O(n),空间复杂度O(n)
List<Integer> ans = new ArrayList<>();
pre(root, ans);
return ans;
}
private void pre(Node node, List<Integer> list) {
if (node == null) {
return;
}
list.add(node.val);
for (Node child : node.children) {
pre(child, list);
}
}
}
class Solution {
public List<Integer> preorder(Node root) {
//法二:迭代.时间复杂度O(n),空间复杂度O(n)
LinkedList<Integer> ans = new LinkedList<>();
if (root == null) {
return ans;
}
LinkedList<Node> stack = new LinkedList<>();
stack.add(root);
while (!stack.isEmpty()) {
Node node = stack.pollLast();
ans.add(node.val);
Collections.reverse(node.children);
for (Node child : node.children) {
stack.add(child);
}
}
return ans;
}
}
2.4 N叉树的后序遍历#590（简单）
https://leetcode-cn.com/problems/n-ary-tree-postorder-traversal/
class Solution {
public List<Integer> postorder(Node root) {
//法一:递归.时间复杂度O(n),空间复杂度O(n)
List<Integer> ans = new ArrayList<>();
post(root, ans);
return ans;
}
private void post(Node node, List<Integer> list) {
if (node == null) {
return;
}
for (Node child : node.children) {
post(child, list);
}
list.add(node.val);
}
}
class Solution {
public List<Integer> postorder(Node root) {
//法二:迭代.时间复杂度O(n),空间复杂度O(n)
LinkedList<Integer> ans = new LinkedList<>();
if (root == null) {
return ans;
}
Deque<Node> stack = new ArrayDeque<>();
stack.addLast(root);
while (!stack.isEmpty()) {
Node node = stack.removeLast();
ans.addFirst(node.val);
for (Node child : node.children) {
stack.addLast(child);
}
}
return ans;
}
}
2.5 N叉树的层序遍历#429（中等）
https://leetcode-cn.com/problems/n-ary-tree-level-order-traversal/
//基于队列的遍历算法模板：
List<Integer> values = new ArrayList<>();
Queue<Node> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
Node nextNode = queue.remove();
values.add(nextNode.val);
for (Node child : nextNode.children) {
queue.add(child);
}
}
class Solution {
public List<List<Integer>> levelOrder(Node root) {
//法一:队列+BFS.时间复杂度O(n),空间复杂度O(n)
List<List<Integer>> ans = new ArrayList<>();
if (root == null) {
return ans;
}
Queue<Node> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
List<Integer> level = new ArrayList<>();
int size = queue.size();
for (int i = 0; i < size; i++) {
Node node = queue.poll();
level.add(node.val);
//这里也可以改成foreach循环，逐个添加
queue.addAll(node.children);
}
ans.add(level);
}
return ans;
}
}
class Solution {
public List<List<Integer>> levelOrder(Node root) {
//法二:简化的BFS.时间复杂度O(n),空间复杂度O(n)
List<List<Integer>> ans = new ArrayList<>();
if (root == null) {
return ans;
}
List<Node> currentLayer = Arrays.asList(root);
while (!currentLayer.isEmpty()) {
List<Node> nextLayer = new ArrayList<>();
List<Integer> previousVals = new ArrayList<>();
for (Node node : currentLayer) {
previousVals.add(node.val);
nextLayer.addAll(node.children);
}
ans.add(previousVals);
currentLayer = nextLayer;
}
return ans;
}
}
class Solution {
public List<List<Integer>> levelOrder(Node root) {
//法三:递归.时间复杂度O(n),空间复杂度O(n)
//一般情况下：递归运行使用堆栈，适合用来做DFS。
//队列适合用来做BFS。
//但是本题中以不同顺序添加到最终列表中，
//只要知道节点在哪一层并确保在那一层的列表顺序正确就可以了。
List<List<Integer>> ans = new ArrayList<>();
if (root != null) {
traverseNode(root, 0, ans);
}
return ans;
}
private void traverseNode(Node node, int level, List<List<Integer>> list) {
if (list.size() <= level) {
list.add(new ArrayList<>());
}
list.get(level).add(node.val);
for (Node child : node.children) {
traverseNode(child, level + 1, list);
}
}
}
若有收获，就点个赞吧
0 人点赞
