递归

比较简单,直接看代码即可.

    private void preOrderRec(TreeNode node,ArrayList<Integer> pre){
        if(node==null) return;
        pre.add(node.val);
        preOrderRec(node.left,pre);
        preOrderRec(node.right,pre);
    }
    
    private void inOrderRec(TreeNode node,ArrayList<Integer> in){
        if(node==null) return;        
        inOrderRec(node.left,in);
        in.add(node.val);
        inOrderRec(node.right,in);
    }
    
    private void postOrderRec(TreeNode node,ArrayList<Integer> post){
        if(node==null) return; 
        postOrderRec(node.left,post);
        postOrderRec(node.right,post);
        post.add(node.val);
    }

非递归

先序遍历

1. 申请一个栈,记为s1,将头结点压栈.
2. 每次从栈顶弹出节点node,打印node的值,如果node的右子节点不为空,压栈.如果node的左子结点不为空,压栈.
3. 重复步骤2直到栈为空.

//非递归版本
    private void preOrder(TreeNode node,ArrayList<Integer> pre){      
       Deque<TreeNode> stack=new ArrayDeque<TreeNode>();
       if(node==null) return;
       stack.push(node);
       while(!stack.isEmpty()){
           node=stack.pop();
           pre.add(node.val);
           if(node.right!=null)stack.push(node.right);
           if(node.left!=null)stack.push(node.left);           
       }
    }

中序遍历

1. 申请一个栈,记为s1,当前节点为node.
2. 将node及其左边界压入栈中,即不断的利用node=node.left并对其压栈,然后重复步骤2.
3. 直到node为空,此时从s1中弹出一个节点,记为node,打印node的值并让node=node.right.转到步骤2.

 private void inOrder(TreeNode node,ArrayList<Integer> in){
        Deque<TreeNode> stack=new ArrayDeque<TreeNode>();
        while(node!=null||!stack.isEmpty()){    
           while(node!=null){
               stack.push(node);
               node=node.left;
           }      
           node=stack.pop();
           in.add(node.val);
           node=node.right;                       
       }        
    }

后序遍历(两个栈实现)

1. 申请一个栈,记为s1,然后将头结点压入s1.
2. 从s1中弹出的节点记为node,先把node的左孩子压入s1中,再把node的右孩子压入s1中.
3. 在整个过程过程中,每个从s1中弹出的节点都压入到s2中.
4. 不断重复2和3,直到s1为空.
5. 依次弹出s2的值就是后序遍历的结果.

 private void postOrder(TreeNode node,ArrayList<Integer> post){
       Deque<TreeNode> stack1=new ArrayDeque<TreeNode>();
       Deque<TreeNode> stack2=new ArrayDeque<TreeNode>();
       if(node==null)return;
       stack1.push(node);
       while(!stack1.isEmpty()){
           node=stack1.pop();
           stack2.push(node);
           if(node.left!=null)stack1.push(node.left);
           if(node.right!=null)stack1.push(node.right);        
       }
       while(!stack2.isEmpty()){
           post.add(stack2.pop().val);
       }
    }