P30-二叉树遍历-层序-迭代

//二叉树遍历
/*
 * 前序遍历：根左右
 * 中序遍历：左根右
 * 后序遍历：左右根
 * 层序遍历：从上往下、从左往右
 *
 * 递归遍历：使用递归方法遍历
 * 迭代遍历：使用迭代方法实现递归函数，与递归等价
 * morris遍历
 * */
public class P30 {

    /*
     *           1
     *         /   \
     *       2       3
     *     /   \
     *   4       5
     *         /   \
     *       6       7
     * */
    public static void main(String[] args) {
        TreeNode node7 = new TreeNode(7, null, null);
        TreeNode node6 = new TreeNode(6, null, null);
        TreeNode node5 = new TreeNode(5, node6, node7);
        TreeNode node4 = new TreeNode(4, null, null);
        TreeNode node3 = new TreeNode(3, null, null);
        TreeNode node2 = new TreeNode(2, node4, node5);
        TreeNode node1 = new TreeNode(1, node2, node3);

        iter(node1);
    }

    //层序-迭代
    //1-2-3-4-5-6-7
    //符合先进先出，用队列
    public static void iter(TreeNode root){

        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);

//        while(!q.isEmpty()){
//            root = q.poll();
//            System.out.println(root.val);
//            if(root.left != null){
//                q.add(root.left);
//            }
//            if(root.right != null){
//                q.add(root.right);
//            }
//        }

        while(!q.isEmpty()){
            root = q.poll();

            if(root != null){
                System.out.println(root.val);
                q.add(root.left);
                q.add(root.right);
            }
        }

    }

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

        TreeNode(){}

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

        TreeNode(int val, TreeNode left, TreeNode right){
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

}