94 二叉树的中序遍历

题目

给定一个二叉树，返回他的中序遍历

分析

递归：中序左——打印——中序右
非递归：空右不空左。设置一个栈，先将头结点压入栈中。head为移动指针。如果当前节点不为空，则将左边全部压入栈。如果当前节点为空，则弹出并打印，找到打印节点的右边，判断是否为空。

代码

//迭代
public void preOrderRecur1(Node head){
    if(head==null){
        return;
    }

    preOrderRecur1(head.left);
    System.out.println(head.value);
    preOrderRecur1(head.right);
}

//非迭代
public void preOrderRecur2(Node head){
    if(head!=null){
        Stack<Node> stack = new Stack<>();
        while(!stack.isEmpty()||head!=null){
            if(head!=null){
                stack.push(head);
                head = head.left;

            }
            else{
                head = stack.pop();
                System.out.println(head.value);
                head = head.right;

            }
        }
    }
    
}