递归
public class Tree {
class TreeNode{
TreeNode left;
TreeNode right;
int val;
}
//二叉树前序遍历
public void preOrderTree(TreeNode root) {
if (root != null) {
System.out.println(root.val + " ");
preOrderTree(root.left);
preOrderTree(root.right);
}
}
//二叉树中序遍历
public void inOrderTree(TreeNode root) {
if (root != null) {
inOrderTree(root.left);
System.out.println(root.val + " ");
inOrderTree(root.right);
}
}
//二叉树后序遍历
public void postOrderTree(TreeNode root) {
if (root != null) {
postOrderTree(root.left);
postOrderTree(root.right);
System.out.println(root.val + " ");
}
}
}
非递归:
public class OrderTree {
class TreeNode{
TreeNode left;
TreeNode right;
int val;
}
//层序遍历
public void levelOrderTree(TreeNode root) {
if (root == null) {
return;
}
LinkedList<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
System.out.println(node.val + " ");
if (node.left!= null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
}
//二叉树前序遍历
public void preOrderTree(TreeNode root) {
if (root != null) {
LinkedList<TreeNode> stack = new LinkedList<>();
TreeNode pNode = root;
while (pNode != null || !stack.isEmpty()) {
if (pNode != null) {
System.out.println(pNode.val+" ");
stack.push(pNode);
pNode = pNode.left;
}else {
TreeNode node = stack.pop();
pNode = node.right;
}
}
}
}
//二叉树中序遍历
public List<Integer> inOrderTree(TreeNode root) {
List<Integer> list = new ArrayList<>();
ArrayDeque<TreeNode> stack = new ArrayDeque<>();
while (root != null || !stack.isEmpty()) {
while (root != null) {
stack.addFirst(root);
root = root.left;
}
root = stack.removeFirst();
list.add(root.val);
root = root.right;
}
return list;
}
//二叉树后序遍历
public List<Integer> postorderTree(TreeNode root) {
List<Integer> list = new ArrayList<>();
Deque<TreeNode> stack = new ArrayDeque<>();
TreeNode pre = null;
while (!stack.isEmpty() || root != null) {
while (root != null) {
stack.push(root);
root = root.left;
}
root = stack.peek();
// i ：判断如果右子树不为空且不为
if (root.right != null && root.right != pre) {
root = root.right;
} else {
root = stack.pop();
list.add(root.val);
pre = root;
root = null;
}
}
return list;
}
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/96863.html
