二叉树的遍历
二叉树的表示
//Java
public class TreeNode{
int val;
Node left,right;
public Node(int val){
this.val=val;
}
}
前序遍历
递归方法
public static void preOrder1(TreeNode root){
if(root == null)
return;
System.out.println(root.val);
preOrder1(root.left);
preOrder1(root.right);
}
非递归方法
public static void preOrder2(TreeNode root){
Stack<TreeNode> stack = new Stack<>();
TreeNode node = root;
while(node != null || !stack.empty()){
if(node != null){
System.out.println(node.val);
stack.push(node);
node = node.left;
}else{
node = stack.pop();
node = node.right;
}
}
}
中序遍历
public static void inOrder1(TreeNode root){
if(root == null)
return;
inOrder1(root.left);
System.out.println(root.val);
inOrder1(root.right);
}
非递归方法
//非递归方法
public static void inOrder2(TreeNode root){
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode node= root;
while(node != null || !stack.empty()){
if(node != null){
stack.push(node);
node = node.left;
}else {
node = stack.pop();
System.out.println(node.val);
node = node.right;
}
}
}
后序遍历
递归方法
public static void postOrder1(TreeNode root){
if(root == null)
return;
postOrder1(root.left);
postOrder1(root.right);
System.out.println(root.val);
}
非递归方法
/*
* 后续遍历
*/
public void lastOrder(Btree<T> root){
Stack<Btree<T>> stack = new Stack<Btree<T>>();
Btree<T> p = root;//保存当前节点
Btree<T> q = null;//记录最后一个输出的节点，用于检验是不是根节点的右节点
while(p != null || !stack.isEmpty()){
//由根节点向下遍历，知道找到该根节点下的最后一个叶子节点
while (p != null) {
stack.push(p);//非叶子节点入栈
p = p.left;//指向该节点的左孩子
}
//p为空，栈非空,说明遍历完了左孩子，处于叶子节点状态
if (!stack.isEmpty()) {
p = stack.pop();//栈顶出栈
//因为如果该节点有右节点，肯定是先访问完右节点才开始访问跟节点的
//p.right == null：表示没有右节点，可以直接访问根节点
//p.right == q:刚访问完该节点右节点，则可以访问我该节点
if (p.right == null || p.right == q) {
visitDate(p);//访问当前节点
q = p;//记录这个节点
p = null;
}else{//开始遍历右孩子
p = p.right;
}
}
}
}
public static void LevelorderTraversal ( TreeNode root )
{
LinkedList<TreeNode> Q = new LinkedList<TreeNode>();
TreeNode node = root;
if ( node == null ) return; /* 若是空树则直接返回 */
Q.offer(node);
while ( !Q.isEmpty() ) {
node = Q.poll();
System.out.println( node.val ); /* 访问取出队列的结点 */
if ( node.left != null ) Q.offer(node.left);
if ( node.right != null ) Q.offer(node.right);
}
}
//计算二叉树的深度
public static int level(BinTree root){
if(root == null){
return 0;
}
int left = level(root.leftChild)+1;
int right = level(root.rightChild)+1;
return left > right? left : right;
}
import java.util.*;
/*
* public class TreeNode {
* int val = 0;
* TreeNode left = null;
* TreeNode right = null;
* }
*/
public class Solution {
/**
*
* @param root TreeNode类 the root of binary tree
* @return int整型二维数组
*/
public int[][] threeOrders (TreeNode root) {
// write code here
int[][] res = new int[3][3];
res[0] = firstorderTraversal(root);
res[1] = inorderTraversal(root);
res[2] = postorderTraversal(root);
return res;
}
// 后续
public int[] postorderTraversal (TreeNode root) {
// write code here
LinkedList<Integer> list = new LinkedList<>();
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode p = root;
TreeNode lastNode = root;
while(!stack.isEmpty() || p != null){
while(p != null){
stack.push(p);
p = p.left;
}
p = stack.peek();
if(p.right == null || p.right == lastNode){
list.add(stack.peek().val);
p = null;
lastNode = stack.pop();
} else{
p = p.right;
}
}
int[] res = new int[list.size()];
for(int i = 0; i < list.size(); i++){
res[i] = list.get(i);
System.out.println(res[i]);
}
return res;
}
// 前序
public int[] firstorderTraversal (TreeNode root) {
// write code here
LinkedList<Integer> list = new LinkedList<>();
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode p = root;
while(!stack.isEmpty() || p != null){
while(p != null){
list.add(p.val);
stack.push(p);
p = p.left;
}
if(!stack.isEmpty()){
p = stack.pop();
p = p.right;
}
}
int[] res = new int[list.size()];
for(int i = 0; i < list.size(); i++){
res[i] = list.get(i);
System.out.println(res[i]);
}
return res;
}
// 中序
public int[] inorderTraversal (TreeNode root) {
// write code here
LinkedList<Integer> list = new LinkedList<>();
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode p = root;
while(!stack.isEmpty() || p != null){
while(p != null){
stack.push(p);
p = p.left;
}
if(!stack.isEmpty()){
list.add(stack.peek().val);
p = stack.pop().right;
}
}
int[] res = new int[list.size()];
for(int i = 0; i < list.size(); i++){
res[i] = list.get(i);
System.out.println(res[i]);
}
return res;
}
}
