leetcode589.N叉树的前序遍历,N590.N叉树的后序遍历
N叉树的前序遍历
N叉树前序遍历的结果为：
[1,3,5,6,2,4]
思路一：recursion
代码如下：
/*
// Definition for a Node.
class Node {
public int val;
public List<Node> children;
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val, List<Node> _children) {
val = _val;
children = _children;
}
};
*/
class Solution {
List<Integer> list = new ArrayList<>();
public List<Integer> preorder(Node root) {
if(root == null){
return list;
}
list.add(root.val);
while(!root.children.isEmpty()){
preorder(root.children.remove(0));
}
return list;
}
}
本代码并没有考虑到维护原二叉树的结构，而是选择使用了remove函数。如果面试的时候遇到此类问题，可以和面试官交流，如果需要保持二叉树的原有结构则可以选择正常的遍历~
时间复杂度：O(N)
额外空间复杂度：O(N)
O(N)为本题最坏情况的额外空间复杂度，也就是二叉树退化为链表时，递归栈的深度为N
执行结果:
思路二：stack
同二叉树的前序遍历相同，二叉树的前序遍历，需要按照先右节点后左节点的顺序入栈。本题则是将arrayList的每一个节点从后向前地push到栈中，本代码依旧没有考虑维护原有的二叉树 :-)
代码如下：
/*
// Definition for a Node.
class Node {
public int val;
public List<Node> children;
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val, List<Node> _children) {
val = _val;
children = _children;
}
};
*/
class Solution {
public List<Integer> preorder(Node root) {
List<Integer> list = new ArrayList<>();
if(root != null){
Stack<Node> stack = new Stack<>();
stack.push(root);
while(!stack.isEmpty()){
root = stack.pop();
list.add(root.val);
while(!root.children.isEmpty()){
stack.push(root.children.remove(root.children.size() - 1));
}
}
}
return list;
}
}
执行结果如下:
N叉树的后序遍历
题目链接
N叉树的后序遍历：
对于上面这棵二叉树，后序遍历的结果为：
[5,6,3,2,4,1]
思路一：recursion
代码如下：
/*
// Definition for a Node.
class Node {
public int val;
public List<Node> children;
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val, List<Node> _children) {
val = _val;
children = _children;
}
};
*/
class Solution {
private List<Integer> list = new ArrayList<>();
public List<Integer> postorder(Node root) {
if(root == null){
return list;
}
List<Node> children = root.children;
while(!children.isEmpty()){
postorder(children.remove(0));
}
list.add(root.val);
return list;
}
}
该算法的时间复杂度:
因为N叉树的每个节点相当于只遍历了一遍，所以时间复杂度为O(N),额外空间上来讲，需要递归栈，最大的递归深度为，N叉树退化为一个链表的时候，额外空间复杂度O(N)
代码执行结果:
思路二：stack
对于一棵树的后序遍历而言，我们只需要使用两个栈，只不过入栈的顺序保证和先序遍历相反即可；关于二叉树的先序后序遍历，请见文章：二叉树基础题
代码如下：
/*
// Definition for a Node.
class Node {
public int val;
public List<Node> children;
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val, List<Node> _children) {
val = _val;
children = _children;
}
};
*/
class Solution {
public List<Integer> postorder(Node root) {
List<Integer> list = new ArrayList<>();
if(root != null){
Stack<Node> stack1 = new Stack<>();
Stack<Node> stack2 = new Stack<>();
stack1.push(root);
while(!stack1.isEmpty()){
root = stack1.pop();
stack2.push(root);
while(!root.children.isEmpty()){
stack1.push(root.children.remove(0));
}
}
while(!stack2.isEmpty()){
list.add(stack2.pop().val);
}
}
return list;
}
}
该算法的时间复杂度为:O(N),额外使用了两个栈，额外空间复杂度为O(N);
代码执行结果惨不忍睹：
查看11道真题和解析