Binary Tree Traversal Method

引言

虽然很不情愿，自从大学里面就没有追根到底的学好数据结构，没有一个个去好好实现它，有的东西知道怎么去写，但是涉及到代码就很头疼，不知道从哪里下手，考研的时候也没有认真去了解。好吧，现在开始相当于从头再来过一遍！

二叉树的前，中，后序遍历概念

这个算是基础中的基础了，反正我依稀记得老师所说的口诀：“前序遍历，根左右；中序遍历，左根右；后序遍历，左右根”。好吧，来看看lintcode上的例子描述
前序遍历：

Given a binary tree, return the preorder traversal of its nodes’ values.
Note
Given binary tree {1,#,2,3},
1
\
2
/
3
return [1,2,3].

中序遍历：

Given a binary tree, return the inorder traversal of its nodes’ values.
Example
Given binary tree {1,#,2,3},
1
\
2
/
3
return [1,3,2].

后序遍历:

Given a binary tree, return the postorder traversal of its nodes’ values.
Example
Given binary tree {1,#,2,3},
1
\
2
/
3
return [3,2,1].

二叉树前中后序遍历的递归实现

如果用递归来做的话，比较简单，拿前序遍历举例子

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */
public class Solution {
    /**
     * @param root: The root of binary tree.
     * @return: Preorder in ArrayList which contains node values.
     */
    public ArrayList<Integer> preorderTraversal(TreeNode root) {
        // write your code here
        ArrayList<Integer> arr = new ArrayList<Integer>();
        traverse(root,arr);
        return arr;
    }
    
    public void traverse(TreeNode root,ArrayList<Integer> arr){
        if(root==null) return;
        arr.add(root.val);
        if(root.left!=null){
            traverse(root.left,arr);
        }
        if(root.right!=null){
            traverse(root.right,arr);
        }
    }
}

二叉树前序遍历的非递归做法

public class Solution {
    /**
     * @param root: The root of binary tree.
     * @return: Preorder in ArrayList which contains node values.
     */
    public ArrayList<Integer> preorderTraversal(TreeNode root) {
        // write your code here
        ArrayList<Integer> arr = new ArrayList<Integer>();
        Stack<TreeNode> s = new Stack<TreeNode>();
        s.push(root);
        while(!s.isEmpty()){
            TreeNode node = s.pop();
            arr.add(node.val);
            if(node.left) s.push(node.left);
            if(node.right) s.push(node.right);
        }
        return arr;
    }
}

引用参考
//非递归中序遍历
public static void inTraverse(BinaryTree root) {
Stack s = new Stack();
BinaryTree p = root;
while(p!=null || !s.isEmpty()) {
if(p!=null) {
s.push(p);
p = p.lchild;
}
else {
p = (BinaryTree)s.pop();
visit(p);
p = p.rchild;
}
}
}
//非递归后序遍历
public static void postTraverse(BinaryTree root) {
Stack s = new Stack();
BinaryTree p = root;
//pre标记最近出栈的节点，用于判断是否是p节点的右孩子，如果是的话，就可以访问p节点
BinaryTree pre = p;
//flag标记是出栈还是继续将左孩子进栈
boolean flag = true;
while(p!=null || !s.isEmpty()) {
if(p!=null && flag) {
s.push(p);
p = p.lchild;
}
else {
if(s.isEmpty()) return;
p = (BinaryTree)s.peek();
if(p.rchild != null && p.rchild!=pre) {
p = p.rchild;
flag = true;
}
else {
p = (BinaryTree)s.pop();
visit(p);
flag = false;
pre = p;
}
}
}
}
//非递归后序遍历2
public static void postTraverse2(BinaryTree root) {
Stack s = new Stack();
BinaryTree p = root;
//pre标记最近出栈的节点，用于判断是否是p节点的右孩子，如果是的话，就可以访问p节点
BinaryTree pre = p;
while(p!=null || !s.isEmpty()) {
if(p!=null) {
s.push(p);
p = p.lchild;
}
else {
if(s.isEmpty()) return;
p = (BinaryTree)s.peek();
if(p.rchild != null && p.rchild!=pre) {
p = p.rchild;
}
else {
p = (BinaryTree)s.pop();
visit(p);
pre = p;
p = null;
}
}
}
}
}

二叉树的层次遍历的实现

二叉树的层次遍历需要使用队列来实现

public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {
    // write your code here
    // 用一个队列存储每层的数，根据
    ArrayList<ArrayList<Integer>> arr = new ArrayList<ArrayList<Integer>>();
    if(root == null) return arr;
    Queue<TreeNode> queue = new LinkedList<TreeNode>();
    queue.offer(root);
    while(queue.size()!=0){
        ArrayList<Integer> array = new ArrayList<Integer>();
        int size = queue.size();
        for(int i=0;i!=size;++i){
            TreeNode node = queue.peek();
            queue.poll();
            array.add(node.val);
            if(node.left!=null){
                queue.offer(node.left);
            }
            if(node.right!=null){
                queue.offer(node.right);
            }
        }
        arr.add(array);
    }
    return arr;
}