树是一种非线性的结构,叫做树是它的结构看起来像一颗倒挂的树。一个结点由一个根节点加上左右子树便成为了二叉树。二叉树在树的有着很重要的位置。大多数题目都是基于二叉树的。
本文主要分享二叉树的几个遍历方式,概念只做简单介绍。二叉树的几个遍历方式如下:
// 前序遍历(递归) void preOrder(TreeNode root); // 中序遍历(递归) void inOrder(TreeNode root); // 后序遍历(递归) void postOrde(TreeNode root); //前序遍历(非递归) public ListpreorderTraversal(TreeNode root); //中序遍历(非递归) public List inorderTraversal(TreeNode root); //后序遍历(非递归) public List postorderTraversal(TreeNode root); //层序遍历 public List > levelOrder(TreeNode root);
前置说明
二叉树的表示方法很多,我们在做题的时候,常常使用孩子表示法。
class TreeNode {
int val;//数值域
TreeNode left;//左孩子(结点)的引用
TreeNode right;//右孩子(结点)的引用
public TreeNode(int val) {
this.val = val;
}
}
自己来创建一颗二叉树,比如下面的一个二叉树:
这里手动创建一个二叉树。
public void createTree() {
TreeNode A = new TreeNode(1);
TreeNode B = new TreeNode(2);
TreeNode C = new TreeNode(3);
TreeNode D = new TreeNode(4);
TreeNode E = new TreeNode(5);
TreeNode F = new TreeNode(6);
TreeNode G = new TreeNode(7);
A.left = B;
A.right = C;
B.left = D;
B.right = E;
C.left = F;
C.right = G;
}
1、前序遍历(递归)
public void preOrder(TreeNode root) {
//如果是空的结点,就返回
if (root == null) return;
//你的操作
System.out.print(root.val + " ");
//走树的左边
preOrder(root.left);
//走树的右边
preOrder(root.right);
}
2、中序遍历(递归)
void inOrder(TreeNode root) {
//如果是空的结点,就返回
if (root == null) return;
//先走树的左边
inOrder(root.left);
//你的操作
System.out.print(root.val + " ");
//走树的右边
inOrder(root.right);
}
3、后序遍历(递归)
void postOrder(TreeNode root) {
//如果是空的结点,就返回
if (root == null) return;
//先走树的左边
postOrder(root.left);
//走树的右边
postOrder(root.right);
//你的操作
System.out.print(root.val + " ");
}
4、前序遍历(非递归)
public List5、中序遍历(非递归)preorderTraversal(TreeNode root) { List res = new ArrayList (); if (root == null) { return res; } Deque stack = new LinkedList<>(); TreeNode node = root; while (!stack.isEmpty() || node != null) { while (node != null) { res.add(node.val); stack.push(node); node = node.left; } node = stack.pop(); node = node.right; } return res; }
public List6、后序遍历(非递归)inorderTraversal(TreeNode root) { List list = new ArrayList<>(); if (root == null) return list; Stack queue = new Stack<>(); while (!queue.isEmpty() || root != null) { while (root != null) { queue.push(root); root = root.left; } root = queue.pop(); list.add(root.val); root = root.right; } return list; }
public List7、层序遍历postorderTraversal(TreeNode root) { List res = new ArrayList (); if (root == null) { return res; } Stack stack = new Stack<>(); TreeNode prev = null; while (root != null || !stack.isEmpty()) { while (root != null) { stack.push(root); root = root.left; } root = stack.pop(); if (root.right == null || root.right == prev) { res.add(root.val); prev = root; root = null; } else { stack.push(root); root = root.right; } } return res; }
public List> levelOrder(TreeNode root) { List
> ret = new ArrayList<>(); if (root == null) return ret; Queue
queue = new LinkedList<>(); queue.offer(root); while (!queue.isEmpty()) { int size = queue.size(); List list = new ArrayList<>(); while (size > 0) { TreeNode cur = queue.poll(); if (cur.left != null) { queue.offer(cur.left); } if (cur.right != null) { queue.offer(cur.right); } list.add(cur.val); --size; } ret.add(list); } return ret; }



