Java实现二叉树的各种操作

最近整理了一下关于二叉树的各种算法题，代码如下，欢迎大家提问与转载，转载请注明出处

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

class TreeNode {
	int val = 0;
	TreeNode left = null;
	TreeNode right = null;

	public TreeNode(int val) {
	    this.val = val;
	}
}

public class BinaryTree {
	//前序遍历：递归法
	static ArrayList<Integer> preList = new ArrayList<Integer>();
	public ArrayList<Integer> preOrder(TreeNode root) {	
		if(root == null)	return preList;	
		preList.add(root.val);

		if(root.left == null && root.right == null) return preList;

		preOrder(root.left);	
		preOrder(root.right);	

		return preList;
	}

	//前序遍历：迭代法,借助栈
	public ArrayList<Integer> preOrder2(TreeNode root) {	
		ArrayList<Integer> preList2 = new ArrayList<Integer>();
		if(root == null)	return preList;	

		Stack<TreeNode> stack = new Stack<TreeNode>();
		stack.push(root);
		while(!stack.isEmpty()) {
			TreeNode temp = stack.pop();
			preList2.add(temp.val);

			if(temp.right != null) {
				stack.push(temp.right);
			}

			if(temp.left != null) {
				stack.push(temp.left);
			}
		}

		return preList2;
	}

	//中序遍历：递归法
	ArrayList<Integer> inList = new ArrayList<Integer>();
	public ArrayList<Integer> inOrder(TreeNode root) {	
		if(root == null)	return inList;	

		if(root.left == null && root.right == null) {	//递归终止条件
			inList.add(root.val);
			return inList;
		}

		inOrder(root.left);	
		inList.add(root.val);
		inOrder(root.right);

		return inList;
	}

	//中序遍历：迭代法,借助栈
	public ArrayList<Integer> inOrder2(TreeNode root) {	
		ArrayList<Integer> inList2 = new ArrayList<Integer>();
		if(root == null)	return inList2;	

		Stack<TreeNode> stack = new Stack<TreeNode>();
		TreeNode node = root;
		while(node != null || !stack.isEmpty()) {
			while(node != null) {	//中序遍历核心思想：添加某个元素之前要添加它的所有左节点
				stack.push(node);
				node = node.left;
			}

			node = stack.pop();
			inList2.add(node.val);
			node = node.right;
		}

		return inList2;
	}

	//后序遍历：递归法
	static ArrayList<Integer> postList = new ArrayList<Integer>();
	public ArrayList<Integer> postOrder(TreeNode root) {	
		if(root == null)	return postList;	

		if(root.left == null && root.right == null) {
			postList.add(root.val);
			return postList;
		}

		postOrder(root.left);
		postOrder(root.right);
		postList.add(root.val);

		return postList;
	}

	//层序遍历：迭代法，借助队列
	public ArrayList<Integer> levelOrder(TreeNode root) {
		ArrayList<Integer> levelList = new ArrayList<Integer>();
		if(root == null) 
			return levelList;
		Queue<TreeNode> queue = new LinkedList<TreeNode>();
		queue.offer(root);

		while(!queue.isEmpty()) {
			TreeNode temp = queue.poll();
			if(temp != null) {
				levelList.add(temp.val);
			}

			if(temp.left != null) {
				queue.offer(temp.left);
			}

			if(temp.right != null) {
				queue.offer(temp.right);
			}
		}

		return levelList;
	}

	//Z字型遍历：迭代法，借助栈
	public ArrayList<Integer> ZOrder(TreeNode root) {
		ArrayList<Integer> ZList = new ArrayList<Integer>();
		if(root == null) 
			return ZList;

		Stack<TreeNode> s1 = new Stack<TreeNode>();	//负责奇数层
		Stack<TreeNode> s2 = new Stack<TreeNode>();	//负责偶数层
		s1.push(root);

		while(!s1.isEmpty() || !s2.isEmpty()) {
			while(!s1.isEmpty()) {
				TreeNode temp = s1.pop();
				ZList.add(temp.val);
				if(temp.left != null) {
					s2.push(temp.left);
				}

				if(temp.right != null) {
					s2.push(temp.right);
				}
			}

			while(!s2.isEmpty()) {
				TreeNode temp = s2.pop();
				ZList.add(temp.val);
				if(temp.right != null) {
					s1.push(temp.right);
				}

				if(temp.left != null) {
					s1.push(temp.left);
				}
			}
		}

		return ZList;
	}

	//求二叉树的深度
	public int getDepth(TreeNode root) {
		if(root == null)
			return 0;

		int leftDepth = getDepth(root.left);
		int rightDepth = getDepth(root.right);

		return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
	}


	public static void main(String[] args) {
		TreeNode root1 = new TreeNode(1);
		root1.left = new TreeNode(2);
		root1.right = new TreeNode(3);

		root1.left.left = new TreeNode(4);
		root1.left.right = new TreeNode(5);
		root1.left.left.left = new TreeNode(8);

		root1.right.left = new TreeNode(6);
		root1.right.right = new TreeNode(7);
		root1.right.right.right = new TreeNode(9);

		BinaryTree t = new BinaryTree();

//		ArrayList<Integer> list = t.ZOrder(root1);
//		for(int i : list) {
//			System.out.print(i + " ");
//		}

		System.out.println(t.getDepth(root1));
	}
}