class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

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

public void visit(TreeNode node) {
    System.out.println(node.val);
}

/**
* 二叉树先序遍历递归实现
* @param root
*/
public void preOrderRecursion(TreeNode root) {
    if(root == null) {
        return;
    }
    visit(root);
    preOrderRecursion(root.left);
    preOrderRecursion(root.right);
}

/**
* 二叉树先序遍历非递归实现
* @param root
* @return
*/
public List<Integer> preOrderTraversal(TreeNode root){
    List<Integer> resultList = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    //1、根节点的null判断
    if(root == null) {
        return null;
    }
    //2、将根节点root压入栈
    stack.push(root);

    //3、while循环，终止条件是stack为空，即栈内元素处理完
    while(!stack.isEmpty()) {
    //4、将栈顶元素pop出，读取并存储结果集
        TreeNode tempNode = stack.pop();
        resultList.add(tempNode.val);
        //5、将取出的元素的右、左子节点分别压入栈，以便循环出栈时是该节点的左、右子节点
        if(tempNode.right != null) {
            stack.push(tempNode.right);
        }
        if(tempNode.left != null) {
            stack.push(tempNode.left);
        }
    }
    return resultList;
}

/**
* 后序遍历的递归实现
* @param root
*/
public void postOrderRecursion(TreeNode root) {
    if (root == null) {
        return;
    }
    postOrderRecursion(root.right);
    postOrderRecursion(root.left);
    visit(root);
}

/**
* 后序遍历的非递归实现
* @param root
* @return
*/
public List<Integer> postOrderTraversal(TreeNode root){
    List<Integer> resultList = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    // 1、根节点的null判断
    if(root == null) {
        return null;
    }
    // 2、将根节点root压入栈
    stack.push(root);
    // 3、while循环，终止条件是stack为空，即栈内元素处理完
    while(!stack.isEmpty()) {
        // 4、将栈顶元素pop出，读取并存储结果集
        TreeNode tempNode = stack.pop();
        resultList.add(tempNode.val);
        // 5、将取出的元素的左、右子节点分别压入栈，以便循环出栈时是该节点的右、左子节点
        if(tempNode.left != null) {
            stack.push(tempNode.left);
        }
        if(tempNode.right != null) {
            stack.push(tempNode.right);
        }
    }
    //6、将结果集进行反转得到后序遍历的结果集
    Collections.reverse(resultList);
    return resultList;
}

/**
* 中序遍历的递归实现
* @param root
*/
public void midOrderRecursion(TreeNode root) {
    if(root == null) {
        return;
    }
    
    midOrderRecursion(root.left);
    visit(root);
    midOrderRecursion(root.right);
}

/**
* 中序遍历的非递归实现
*
* @param root
* @return
*/
public List<Integer> midOrderTraversal(TreeNode root) {
    List<Integer> resultList = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    // 1、对root进行null值判断
    if (root == null) {
        return null;
    }
    // 2、while循环，终止条件为stack为空，即站内所有元素都处理完，或者root!=null
    while (!stack.isEmpty() || root != null) {
        // 3、首先针对当前节点，一直对其左子节点树遍历并将其非空节点入栈
        while (root != null) {
            stack.push(root);
            root = root.left;
        }
        // 4、节点指针迭代为空（到底了）后不再入栈，然后取栈顶元素，存取结果集
        TreeNode tempNode = stack.pop();
        resultList.add(tempNode.val);
        // 5、将当前指针用出栈的节点的右子节点替代，然后回到第3步继续迭代，直到当前节点为空，且栈也为空即遍历完成
        root = root.right;
    }
    return resultList;
}

/**
* 层序遍历
* @param root
* @return
*/
public List<Integer> leverTraversal(TreeNode root) {
    List<Integer> resultList = new ArrayList<>();
    Queue<TreeNode> queue = new ArrayDeque<TreeNode>();
    if (root == null) {
        return null;
    }
    queue.add(root);
    while (!queue.isEmpty()) {
        TreeNode tempNode = queue.peek();
        resultList.add(tempNode.val);
        if (root.left != null) {
            queue.add(root.left);
        }
        if (root.right != null) {
            queue.add(root.right);
        }
        queue.poll();
    }
return resultList;
}

/**
* 计算二叉树的深度
*
* @param root
* @return
*/
public int countBinaryTreeDepth(TreeNode root) {
    if (root == null) {
        return 0;
    }
    int nleft = countBinaryTreeDepth(root.left);
    int nright = countBinaryTreeDepth(root.right);
    return (nleft > nright) ? (nleft + 1) : (nright + 1);
}