先序遍历
/**
* 先序遍历：递归实现
* @param root
*/
public void preOrderRe(TreeNode root){
System.out.print(root.val);
if(root.left != null) {
preOrderRe(root.left);
}
if(root.right != null) {
preOrderRe(root.right);
}
}
/**
* 先序遍历非递归实现：堆栈
* @param root
* @return
*/
public void preOrder(TreeNode root) {
Stack<TreeNode> stack = new Stack<TreeNode>();
while(root != null || !stack.isEmpty()) {
while(root != null) {
System.out.print(root.val);
stack.push(root);
root = root.left;
}
if(!stack.isEmpty()) {
root = stack.pop();
root = root.right;
}
}
}
中序遍历
/**
* 中序遍历递归实现
* @param root
*/
public void midOrderRe(TreeNode root){
if(root.left != null)midOrderRe(root.left);
System.out.print(root.val);
if(root.right != null)midOrderRe(root.right);
}
/**
* 中序遍历非递归实现
* @param root
*/
public void midOrder(TreeNode root){
Stack<TreeNode> stack = new Stack<TreeNode>();
while(root != null || !stack.isEmpty()) {
while(root != null) {
stack.push(root);
root = root.left;
}
if(!stack.isEmpty()) {
root = stack.pop();
System.out.print(root.val);
root = root.right;
}
}
}
后序遍历
/**
* 后序遍历递归实现
* @param root
*/
public void postOrderRe(TreeNode root){
if(root.left != null)postOrderRe(root.left);
if(root.right != null)postOrderRe(root.right);
System.out.print(root.val);
}
/**
* 后序遍历非递归实现
* @param root
*/
public void postOrder1(TreeNode root) {
Stack<TreeNode> stack = new Stack<TreeNode>();
Stack<Integer> output = new Stack<Integer>(); //倒着存排序结果
while(root != null || !stack.isEmpty()) {
while(root != null) {
output.push(root.val);
stack.push(root);
root = root.right;
}
if(!stack.isEmpty()) {
root = stack.pop();
root = root.left;
}
}
while(!output.isEmpty()) {
System.out.print(output.pop());
}
}
层次遍历
//使用数组下标表示深度（深度遍历+层次输出）
ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
support(pRoot,0);
return result;
}
public void support(TreeNode pRoot, int depth){
if(pRoot == null)return ;
if(depth >= result.size()){
result.add(new ArrayList<Integer>());
}
result.get(depth).add(pRoot.val);
support(pRoot.left,depth+1);
support(pRoot.right,depth+1);
}
/**
* 层次遍历使用队列
* @param root
*/
public void levelOrder(TreeNode root) {
if(root == null)return;
Queue<TreeNode> q = new LinkedList<TreeNode>();
q.add(root);
while(!q.isEmpty()) {
int count = q.size();
while(count > 0) {
TreeNode temp = q.poll();
System.out.print(temp.val);
if(temp.left != null)q.add(temp.left);
if(temp.right != null)q.add(temp.right);
count--;
}
}
}