- 二叉树基本概念
二叉树是每个结点至多有两颗子树的树，子树有左右之分，其次序不能任意颠倒。 - 几种特殊二叉树
1） 满二叉树：高度为h，并且含有2h-1个结点的二叉树。即树的每一层都是满的（每层结点数为2(h-1)） 。若对满二叉树编号，从上自下，从左至右，根节点编号为1，则对于编号为i 的结点，如果有双亲，则双亲为⌊i/2⌋，如果有左孩子，左孩子为2i，如果有右孩子，右孩子为2i+1.如下图所示：
满二叉树.png
2） 完全二叉树：若1个高度为h，含有n个结点的二叉树，按照从上自下，从左至右的顺序对结点进行编号，1~n的结点与满二叉树一一对应，则该二叉树为完全二叉树。如下图所示：
完全二叉树.png
3） 二叉排序树：左子树上所有关键字均小于根节点关键字，右子树所有结点关键字均大于根节点关键字。左子树和右子树又各是一颗二叉排序树。
4） 平衡二叉树：树上任一结点的左子树和右子树的深度之差不超过1。 - 二叉树遍历
二叉树定义
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
非递归实现借助栈，前序、中序、后序是相对于根节点而言，根据根节点输出的位置，根、左、右为前序遍历；左、根、右为中序遍历；左、右、根为后序遍历。
1） 前序遍历(PreOrder)：
如果二叉树为空，则什么也不做；否则：
a)访问根节点；
b)先序遍历左子树；
c)先序遍历右子树。
递归实现：
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
if(root == null)
return list;
helper(root, list);
return list;
}
public void helper(TreeNode root, List<Integer> list) {
list.add(root.val);
if(root.left != null)
helper(root.left, list);
if(root.right != null)
helper(root.right, list);
}
常规版非递归实现：先将根节点入栈，然后弹出（访问根节点），然后将其右结点入栈，再将其左结点入栈（栈是先进后出，我们需要先访问左结点，所以先将右结点入栈），然后弹出左结点，对左结点也进行同样的操作（右结点先入栈，左结点入栈），直至栈为空并且访问完了所有结点。
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
if(root == null)
return list;
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while(!stack.isEmpty()) {
root = stack.pop();
list.add(root.val);
if(root.right != null)
stack.push(root.right);
if(root.left != null)
stack.push(root.left);
}
return list;
}
简单版非递归实现：与上一种方式的不同是在访问根节点的时机不相同。常规方式是在出栈时访问根节点，将其写入list中，而简单方式是入栈的同时将值写入list，所以我们只要保证按照前序遍历的顺序去遍历二叉树即可。
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
Deque<TreeNode> stack = new ArrayDeque<>();
TreeNode node = root;
while(node != null || !stack.isEmpty()) {
if(node != null) {
stack.push(node);
list.add(node.val);
node = node.left;
}else {
node = stack.pop();
node = node.right;
}
}
return list;
}
2） 中序遍历(InOrder)：
如果二叉树为空，则什么也不做；否则：
a)中序遍历左子树；
b)访问根节点；
c)中序遍历右子树。
递归实现：
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
if(root == null)
return list;
helper(root, list);
return list;
}
public void helper(TreeNode root, List<Integer> list) {
if(root.left != null)
helper(root.left, list);
list.add(root.val);
if(root.right != null)
helper(root.right, list);
}
常规版非递归实现：从根节点依次遍历左结点，如果左结点没有被访问过，则入栈，当没有左结点或左结点被访问过的时候，弹出栈顶元素，将其写入list，并将其右结点入栈。重复上述操作。
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
Map<TreeNode, Integer> map = new HashMap<>();
Stack<TreeNode> stack = new Stack<>();
if(root == null)
return list;
stack.push(root);
while(!stack.isEmpty()) {
root = stack.peek();
while(root.left != null) {
if(map.containsKey(root.left))
break;
stack.push(root.left);
root = root.left;
}
root = stack.pop();
list.add(root.val);
map.put(root, 1);
if(root.right != null)
stack.push(root.right);
}
return list;
}
简单版非递归实现:从根节点依次将左结点入栈，当没有左结点的时候，弹出栈顶元素，将其写入list，并将其右结点入栈。重复上述操作。与常规方法相比，省去了查看左子树是否被访问过的步骤，对每个结点，都是先遍历其左子树，所以当访问到该结点的时候，可以确保其左子树已经被访问过了，只需要访问其本身和其右结点即可。
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
Deque<TreeNode> stack = new ArrayDeque<>();
TreeNode node = root;
while(node!=null || !stack.isEmpty()) {
if(node != null) {
stack.push(node);
node = node.left;
}else {
node = stack.pop();
list.add(node.val);
node = node.right;
}
}
return list;
}
3） 后序遍历(PostOrder)：
如果二叉树为空，则什么也不做；否则：
a)后序遍历左子树；
b)后序遍历右子树；
c)访问根节点。
递归实现：
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
if(root == null)
return list;
helper(root, list);
return list;
}
public void helper(TreeNode root, List<Integer> list) {
if(root.left != null)
helper(root.left, list);
if(root.right != null)
helper(root.right, list);
list.add(root.val);
}
常规版非递归实现：将根节点左子树入栈，当访问到叶子结点，出栈，查看该叶子结点的父节点是否有右结点，有的话，如果右结点未访问则将其入栈，当一个节点的左右结点都已经访问过或者不包含左右结点，则出栈。
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
Map<TreeNode, Integer> map = new HashMap<>();
Stack<TreeNode> stack = new Stack<>();
if(root == null)
return list;
stack.push(root);
while(!stack.isEmpty()) {
root = stack.peek();
if(root.left == null && root.right == null) {//不含左右结点时，出栈
root = stack.pop();
list.add(root.val);
map.put(root, 1);
}else if((root.left!=null && root.right == null && map.containsKey(root.left))||(root.right != null && root.left == null && map.containsKey(root.right)) || (root.left != null && root.right != null && map.containsKey(root.left) && map.containsKey(root.right))){//包含子节点，但是子节点被访问过，出栈
root = stack.pop();
list.add(root.val);
map.put(root, 1);
}else {
while(root.left != null) {
if(map.containsKey(root.left)) {
break;
}
stack.push(root.left);
root = root.left;
}
if(root.right != null) {
if(map.containsKey(root.right)) {
break;
}
stack.push(root.right);
}
}
}
return list;
}
简单版非递归实现：后序遍历的输出顺序是左、右、根，当我们采用先序遍历的方法，但是先遍历右子树，实现的效果是根、右、左，刚好和后序遍历的结果想法，所以我们通过add(0, node)的方式将顺序反序，达到我们想要的效果。
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
Deque<TreeNode> stack = new ArrayDeque<>();
TreeNode node = root;
while(node != null || !stack.isEmpty()) {
if(node != null) {
stack.push(node);
list.add(0, node.val);
node = node.right;
}else {
node = stack.pop();
node = node.left;
}
}
return list;
}
- 层次遍历：将二叉树按层输出，借助队列实现。借助null来标记一层的结束。当读取到的结点不是null，将该结点的左右结点入队列，当读到null，如果此时队列不空，则继续入null标志新的一层的结尾。
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> list = new ArrayList<>();
if(root == null)
return list;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
queue.add(null);
int num = 0;
List<Integer> tempList = new ArrayList<>();
list.add(tempList);
while(!queue.isEmpty()) {
TreeNode temp = queue.poll();
if(temp != null) {
list.get(num).add(temp.val);
if(temp.left != null)
queue.add(temp.left);
if(temp.right != null)
queue.add(temp.right);
}else {
if(!queue.isEmpty()) {
num++;
tempList = new ArrayList<>();
list.add(tempList);
queue.add(null);
}
}
}
return list;
}
参考：
Preorder, Inorder, and Postorder Iteratively Summarization
二叉树的几种遍历递归与非递归java实现
网友评论