二叉树遍历（前序、中序、后序、层次、深度优先、广度优先遍历）

一、前序遍历

    ArrayList<Integer> res = new ArrayList();
    public void preOrderTraverse1(TreeNode root) {
        if (root != null) {
         // System.out.print(root.val+"  ");
            res.add(root.val);
            preOrderTraverse1(root.left);
            preOrderTraverse1(root.right);
        }
    }

二：中序遍历

    ArrayList<Integer> res = new ArrayList();
    public void inorder(TreeNode root) {
        if (root == null) {
            return;
        }
        inorder(root.left);
        res.add(root.val);
        inorder(root.right);
    }

三：后续遍历

    ArrayList<Integer> res = new ArrayList();
    public  void postorderTraversal(TreeNode root)
    {
        if (root == null) {
            return;
        }
        postorderTraversal(root.left);    
        postorderTraversal(root.right);
        res.add(root.val);
    }

四、层次遍历：

层次遍历的代码比較简单。仅仅须要一个队列就可以。先在队列中增加根结点。之后对于随意一个结点来说。在其出队列的时候，訪问之。同一时候假设左孩子和右孩子有不为空的。入队列。代码例如以下：

    ArrayList<Integer> res = new ArrayList();
    public void levelTraverse(TreeNode root) {
        if (root == null) {
            return;
        }
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        res.add(root.val);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            //System.out.print(node.val+"  ");
            res.add(node.val);
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
    }

五、深度优先遍历

事实上深度遍历就是上面的前序、中序和后序。可是为了保证与广度优先遍历相照顾，也写在这。代码也比較好理解，事实上就是前序遍历，代码例如以下：

二叉树遍历（前序、中序、后序、层次、深度优先、广度优先遍历）

相关推荐