树、二叉树的前中后层序遍历(递归、非递归Java实现)

1. 二叉树的前中后序遍历(递归,非递归)以及层序遍历

1.1 二叉树前中后遍历的递归解法

树的前中后序的遍历这个是很常见的问题,其递归做法相对简单,这里直接贴代码:

    // 前序遍历
    public static void preorder(TreeNode treeNode) {
        if (treeNode == null) return;
        System.out.print(treeNode.val + " ");
        preorder(treeNode.left);
        preorder(treeNode.right);
    }
    
    // 中序遍历
    public static void inorder(TreeNode treeNode) {
        if (treeNode == null) return;
        inorder(treeNode.left);
        System.out.print(treeNode.val + " ");
        inorder(treeNode.right);
    }

    // 后序遍历
    public static void postorder(TreeNode treeNode) {
        if (treeNode == null) return;
        postorder(treeNode.left);
        postorder(treeNode.right);
        System.out.print(treeNode.val + " ");
    }

从上面的代码中可以看到,树的前中后序遍历代码结构基本相同,差距只要在何时输出根值,前序遍历一遍历到节点时,先输出根植,中序是遍历完左子节点,后序是最后才输出,理解起来很容易。

1.2 二叉树前中后遍历的非递归解法

接下来我们来看看如何用非递归的方式,实现前中后序遍历:

1.2.1 非递归的前序遍历:(LeetCode 144)

在这里插入图片描述
前序遍历:34、35、29、25、33、42、40、39
根据树前序遍历的特点,我们很容易将其与栈的特点相结合,这里简单附上代码:

    // 前序遍历的非递归解法
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> lists = new ArrayList<>();
        if (root == null) return lists;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        TreeNode temp = null;
        while (!stack.isEmpty()) {
            temp = stack.pop();
            lists.add(temp.val);
            // 这里注意,要先压入右子节点,再压入左节点
            if (temp.right != null) {
                stack.push(temp.right);
            }
            if (temp.left != null) {
                stack.push(temp.left);
            }
        }
        return lists;
    }

1.2.2 非递归的中序遍历:(LeetCode 94)

在这里插入图片描述
中序遍历:25、29、35、33、34、40、42、39
这个实现的思路,是按照中序遍历的过程:先找到最左的子树,然后返回其父节点,然后遍历右子树,这个返回的动作可以让我们联想到使用栈这个数据结构,实现代码:

    // 二叉树非递归的中序遍历
    public List<Integer> inorderTraversal(TreeNode root) {
    	if (root == null) {
    		return new ArrayList<>();
    	}
        Stack<TreeNode> stack = new Stack<>();
        TreeNode node = root, temp = null;
        List<Integer> lists = new ArrayList<>();
        
        // 判断条件:所有栈为空,且节点指向为空,即所有节点已经完成遍历
        while (!stack.isEmpty() || node != null) {
            // 向左搜索,寻找最左的节点,即中序遍历的第一个节点
            while (node != null) {
                stack.add(node);
                node = node.left;
            }
            // 对每一个节点进行判断
            if (!stack.empty()) {
                // 获取当前节点
                temp = stack.pop();
                // 遍历该节点
                lists.add(temp.val);
                // 如果该节点为内部节点,则按中序遍历的顺序,遍历其右子节点
                node = temp.right;
            }
        }
        return lists;
    }

1.2.3 非递归的后序遍历:(LeetCode 145)

非递归的后序遍历比较麻烦,但如果我们发现以下规律,就会变得简单:
例如:
在这里插入图片描述
对于后序遍历,结果:25、29、33、35、40、39、42、34
后序遍历的方法,就是先左子树,后右子树,再最后根节点,如果反过来,顺序就变成了:先根节点,后右子树,再左子树,是不是跟先序遍历有点像呢?就是先序遍历根节点遍历之后,下一个是遍历左子树,而下一个再遍历右子树。我们按这种反过来的顺序进行遍历,结果:34、42、39、40、35、33、29、25。很容易发现跟上面后序遍历的结果刚好相反。
因此,后序遍历可以变为:先遍历根节点,后遍历右子树,再遍历左子树,的结果的逆序,我们修改先序遍历的代码,可以得到:

    public List<Integer> postorderTraversal_(TreeNode root) {
        LinkedList<Integer> lists = new LinkedList<>();
        if (root == null) return lists;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        TreeNode temp = null;
        while (!stack.isEmpty()) {
            temp = stack.pop();
            lists.addFirst(temp.val);
            if (temp.left != null) {
                stack.push(temp.left);
            }
            if (temp.right != null) {
                stack.push(temp.right);
            }
        }
        return lists;
    }

这里使用了LinkedList,目的是为了让我们每一次插入结果,都可以插入到当前结果的最前面,相当于实现逆序的过程。

1.3 层序遍历:(LeetCode 102、103、107)

层序遍历,就是按照每一层的顺序,一层一层的访问,例如:
在这里插入图片描述
层序遍历的结果为:[[34], [35, 42], [29, 33, 40, 39], [25]]

    // 根据层序遍历的特点,我们很容易想到使用队列,利用广度优先遍历的方式,进行遍历
    public List<List<Integer>> levelOrder(TreeNode root) {
        if (root == null) {
            return new ArrayList<>();
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        List<List<Integer>> lists = new ArrayList<>();
        List<Integer> arrays = new ArrayList<>();
        TreeNode temp = null;
        while (!queue.isEmpty()) {
            int n = queue.size();
            // 这里通过读取队列的元素,获取这一层有多少个元素
            for (int i = 0; i < n; i++) {
                temp = queue.poll();
                arrays.add(temp.val);
                if (temp.left != null) {
                    queue.add(temp.left);
                }
                if (temp.right != null) {
                    queue.add(temp.right);
                }
            }
            // 将每一层的数据放入到链表中
            lists.add(new ArrayList<>(arrays));
            arrays.clear();
        }
        return lists;
    }

2 树的前中后层序遍历

上面讲的都是二叉树,那对于一棵普通的树,其前中后序遍历,是如何呢:

2.1 前序遍历:(LeetCode 589)

	// 递归实现
	public List<Integer> preorder(Node root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        helper(result, root);
        return result;
    }

    private void helper(List<Integer> list, Node root) {
        list.add(root.val);
        for (Node node: root.children
             ) {
            helper(list, node);
        }
    }
    
    // 非递归的N叉树前序遍历
    public List<Integer> preorder(Node root) {
   		List<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }

        Stack<Node> stack = new Stack<>();
        stack.add(root);
        while (!stack.isEmpty()) {
            Node temp = stack.pop();
            result.add(temp.val);
			// 注意这里要入栈的顺序是从右边最后一个子树开始
            for (int i = temp.children.size() - 1; i >= 0; i--) {
                stack.add(temp.children.get(i));
            }
        }

        return result;

2.2 中序遍历:

发现 LeetCode 没有N叉树的中序遍历,关于中序遍历,我们要注意:先遍历最左的一个子树,然后根节点,然后才是遍历其他子节点。
在这里插入图片描述
遍历结果:5、3、6、1、2、4

2.3 后序遍历:(LeetCode 590)

在这里插入图片描述
后序遍历:5、6、3、2、4、1
规律:遍历每个节点,先遍历节点的子节点,最后输入根节点。
这里可以参考二叉树的后序遍历,也使用逆转考虑的方法,先遍历根节点,然后按逆序访问孩子节点,最后将结果进行逆序处理。

    // 递归实现:
    public List<Integer> postorder(Node root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        helper(result, root);
        return result;
    }

    private void helper(List<Integer> list, Node root) {
        for (Node node : root.children
        ) {
            helper(list, node);
        }
        list.add(root.val);
    }

	// 非递归:
	public List<Integer> postorder(Node root) {
        List<Integer> list = new ArrayList<>();
        if (root == null) return list;
        
		Stack<Node> stack = new Stack<>();
        stack.add(root);
        while (!stack.isEmpty()) {
            Node temp = stack.pop();
            result.add(temp.val);
            stack.addAll(temp.children);
        }
        // 将结果进行逆序
        Collections.reverse(list);
        return list;
    }

2.4 层序遍历:(LeetCode 429)

    // N叉树的层序遍历
    public List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> lists = new ArrayList<>();
        if (root == null) {
        	return lists;
        }
        
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        List<Integer> list = new ArrayList<>();
        Node temp = null;
        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            for (int i = 0; i < levelSize; i++) {
                temp = queue.poll();
                // 跟二叉树的层序遍历的区别在于,这里加入的是所有子树
                queue.addAll(temp.children);
                list.add(temp.val);
            }
            lists.add(new ArrayList<>(list));
            list.clear();
        }
        
        return lists;
    }

版权声明:本文为Applying原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接和本声明。