标签：遍历 return cur 多叉树 list right 二叉树 null root
/**
* 十分强大的遍历二叉树类
* 该类包含了二叉树的前中后序遍历，分别用递归、迭代、Morris实现
* 以及二叉树的层序遍历，多叉树的前后序遍历，递归、迭代实现，多叉树的层序遍历
* 讲解方面全都在另一个类TreeUtils中呈现
*
* @name:TreeTraversal
* @author:kallen
* @time:2022/10/30 17:28
*/
public class TreeTraversal {
/*二叉树-前序遍历-递归*/
List<Integer> preList = new ArrayList<>();
public List<Integer> preorderInRecursion(TreeNode root) {
if (root == null) return preList;
preList.add(root.val);
preorderInRecursion(root.left);
preorderInRecursion(root.right);
return preList;
}
/*二叉树-前序遍历-迭代*/
public List<Integer> preorderInIteration(TreeNode root) {
ArrayList<Integer> list = new ArrayList<>();
if (root == null) return list;
Stack<TreeNode> stack = new Stack<>();
while (!stack.isEmpty() || root != null) {
while (root != null) {
stack.push(root);
list.add(root.val);
root = root.left;
}
root = stack.pop().right;
}
return list;
}
/*二叉树-前序遍历-Morris*/
public List<Integer> preorderInMorris(TreeNode root) {
ArrayList<Integer> list = new ArrayList<>();
if (root == null) return list;
TreeNode mostRight;
TreeNode cur = root;
while (cur != null) {
mostRight = cur.left;
if (mostRight != null) {
while (mostRight.right != null && mostRight.right != cur) {
mostRight = mostRight.right;
}
if (mostRight.right == null) {
mostRight.right = cur;
list.add(cur.val);
cur = cur.left;
continue;
} else {
mostRight.right = null;
}
} else {
list.add(cur.val);
}
cur = cur.right;
}
return list;
}
/*二叉树-中序遍历-递归*/
ArrayList<Integer> inList = new ArrayList<>();
public List<Integer> inorderInRecursion(TreeNode root) {
if (root == null) return null;
inorderInRecursion(root.left);
inList.add(root.val);
inorderInRecursion(root.right);
return inList;
}
/*二叉树-中序遍历-迭代*/
public List<Integer> inorderInIteration(TreeNode root) {
ArrayList<Integer> list = new ArrayList<>();
if (root == null) return list;
Stack<TreeNode> stack = new Stack<>();
while (!stack.isEmpty() || root != null) {
while (root != null) {
stack.push(root);
root = root.left;
}
root = stack.pop();
list.add(root.val);
root = root.right;
}
return list;
}
/*二叉树-中序遍历-Morris*/
public List<Integer> inorderInMorris(TreeNode root) {
ArrayList<Integer> list = new ArrayList<>();
if (root == null) return list;
TreeNode cur = root, mostRight;
while (cur != null) {
mostRight = cur.left;
if (mostRight != null) {
while (mostRight.right != null && mostRight.right != cur) {
mostRight = mostRight.left;
}
if (mostRight.right == null) {
mostRight.right = cur;
cur = cur.left;
continue;
} else {
mostRight.right = null;
}
}
list.add(cur.val);
cur = cur.right;
}
return list;
}
/*二叉树-后序遍历-递归*/
ArrayList<Integer> postList = new ArrayList<>();
public List<Integer> postorderInRecursion(TreeNode root) {
if (root == null) return postList;
postorderInRecursion(root.left);
postorderInRecursion(root.right);
postList.add(root.val);
return postList;
}
/*二叉树-后序遍历-迭代*/
public List<Integer> postorderInIteration(TreeNode root) {
ArrayList<Integer> list = new ArrayList<>();
if (root == null) return list;
Stack<TreeNode> stack = new Stack<>();
TreeNode pre = null;
while (!stack.isEmpty() || root != null) {
while (root != null) {
stack.push(root);
pre = root;
root = root.left;
}
root = stack.pop();
if (root.right == null || root.right == pre) {
list.add(root.val);
pre = root;
root = null;
} else {
stack.push(root);
root = root.right;
}
}
return list;
}
/*二叉树-后序遍历-Morris*/
public List<Integer> postorderInMorris(TreeNode root) {
ArrayList<Integer> list = new ArrayList<>();
if (root == null) return list;
TreeNode cur = root, mostRight;
while (cur != null) {
mostRight = cur.left;
if (mostRight != null) {
while (mostRight.right != null && mostRight.right != cur) {
mostRight = mostRight.right;
}
if (mostRight.right == null) {
mostRight.right = cur;
cur = cur.left;
continue;
} else {
mostRight.right = null;
addPath(list, cur.left);
}
}
cur = cur.right;
}
addPath(list, root);
return list;
}
public void addPath(List<Integer> list, TreeNode node) {
int i = list.size();
while (node != null) {
list.add(node.val);
node = node.right;
}
int j = list.size() - 1;
while (i < j) {
int tmp = list.get(i);
list.set(i, list.get(j));
list.set(j, tmp);
i++;
j--;
}
}
/*多叉树-前序遍历-递归*/
ArrayList<Integer> preMultiList = new ArrayList();
public List<Integer> preorderMultipleInRecursion(Node root) {
if (root == null) return preMultiList;
preMultiList.add(root.val);
for (Node child : root.children) {
preorderMultipleInRecursion(child);
}
return preMultiList;
}
/*多叉树-前序遍历-迭代*/
public List<Integer> preorderMultipleInIteration(Node root) {
List<Integer> list = new ArrayList<>();
if (root == null) return list;
Stack<Node> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
Node pop = stack.pop();
list.add(pop.val);
for (int i = pop.children.size() - 1; i >= 0; i--) {
stack.push(pop.children.get(i));
}
}
return list;
}
/*多叉树-后序遍历-递归*/
ArrayList<Integer> postMultiList = new ArrayList<>();
public List<Integer> postorderMultipleInRecursion(Node root) {
if (root == null) return postMultiList;
for (int i = 0; i < root.children.size(); i++) {
postorderMultipleInRecursion(root.children.get(i));
}
postMultiList.add(root.val);
return postMultiList;
}
/*多叉树-后序遍历-迭代*/
public List<Integer> postorderMultipleInIteration(Node root) {
ArrayList<Integer> list = new ArrayList<>();
if (root == null) return list;
Stack<Node> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
Node pop = stack.pop();
if (pop != null) {
stack.push(pop);
stack.push(null);
for (int i = pop.children.size() - 1; i >= 0; i--) {
stack.push(pop.children.get(i));
}
} else {
list.add(stack.pop().val);
}
}
return list;
}
/*二叉树层序遍历*/
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if (root == null) return res;
ArrayDeque<TreeNode> deque = new ArrayDeque<>();
deque.add(root);
int size;
while (!deque.isEmpty()) {
size = deque.size();
ArrayList<Integer> list = new ArrayList<>();
for (int i = size; i > 0; i--) {
TreeNode poll = deque.poll();
list.add(poll.val);
if (poll.left != null) deque.add(poll.left);
if (poll.right != null) deque.add(poll.right);
}
res.add(list);
}
return res;
}
/*多叉树层序遍历*/
public List<List<Integer>> levelOrder(Node root) {
List<List<Integer>> res = new ArrayList<>();
if (root == null) return res;
ArrayDeque<Node> deque = new ArrayDeque<>();
deque.add(root);
int size;
while (!deque.isEmpty()) {
size = deque.size();
ArrayList<Integer> list = new ArrayList<>();
for (int i = size; i > 0; i--) {
Node poll = deque.poll();
list.add(poll.val);
for (Node child : poll.children) {
deque.add(child);
}
}
res.add(list);
}
return res;
}
public static void main(String[] args) {
TreeNode treeNode3 = new TreeNode(3);
TreeNode treeNode2 = new TreeNode(2,treeNode3,null);
TreeNode treeNode1 = new TreeNode(1,null,treeNode2);
TreeTraversal treeTraversal = new TreeTraversal();
List<Integer> list = treeTraversal.postorderInMorris(treeNode1);
}
}
标签：遍历,
return,
cur,
多叉树,
list,
right,
二叉树,
null,
root
From： https://www.cnblogs.com/atomo/p/treetraversal.html