二叉树的遍历

1.二叉树的遍历

二叉树主要有两种遍历方式:

深度优先遍历:先往深走,遇到叶子节点再往回走。

  • 前序遍历(递归法,迭代法) 中左右
  • 中序遍历(递归法,迭代法) 左中右
  • 后序遍历(递归法,迭代法) 左右中

广度优先遍历:一层一层的去遍历。

  • 层次遍历(迭代法)

     二叉树的遍历插图

 

 

 对比图可以理解一下遍历的过程,前中后序遍历涉及递归和迭代两种方法讲解。

2.LeetCode链接

前序遍历:https://leetcode.cn/problems/binary-tree-preorder-traversal/submissions/

中序遍历:https://leetcode.cn/problems/binary-tree-inorder-traversal/submissions/

后序遍历:https://leetcode.cn/problems/binary-tree-postorder-traversal/submissions/

层序遍历:https://leetcode.cn/problems/binary-tree-level-order-traversal/submissions/

感兴趣的可以去练练手!!!

3.前序遍历

前序遍历的顺序是中左右,即先根节点、左子树、右子树,那么我们先考虑递归进行求解。

要打印出前序遍历节点的数值,所以参数里需要放节点的数值,除了这一点就不需要在处理什么数据了也不需要有返回值,所以递归函数返回类型就是void

   Traversal(TreeNode root, List list) 

当前遍历的节点是空了,那么本层递归就要要结束了,所以如果当前遍历的这个节点是空,就直接return

 if (cur == NULL) return; 

前序遍历是中左右的循序,所以在单层递归的逻辑,是要先取中节点的数值

list.add(root.val);

Traversal(root.left, list);

Traversal(root.right, list); 

所以总体的递归代码如下:

class Solution {
    public List preorderTraversal(TreeNode root) {
        List result = new ArrayList();
        preorder(root, result);
        return result;
    }

    public void preorder(TreeNode root, List result) {
        if (root == null) {
            return;
        }
        result.add(root.val);
        preorder(root.left, result);
        preorder(root.right, result);
    }
}

对于迭代法,难度会更大一点!!!

前序遍历是中左右,每次先处理的是中间节点,那么先将根节点放入栈中,然后将右孩子加入栈,再加入左孩子。为什么要先加入 右孩子,再加入左孩子呢? 因为这样出栈的时候才是中左右的顺序

所以我们不难写出代码如下:

class Solution {
    public List preorderTraversal(TreeNode root) {
        List result = new ArrayList();
        if (root == null){
            return result;
        }
        Stack stack = new Stack();
        stack.push(root);
        while (!stack.isEmpty()){
            TreeNode node = stack.pop();
            result.add(node.val);
            if (node.right != null){
                stack.push(node.right);
            }
            if (node.left != null){
                stack.push(node.left);
            }
        }
        return result;
    }
}

4.中序遍历

中序遍历的顺序是左中右,即先左子树、根节点、右子树,那么我们先考虑递归进行求解。

  思路和上面一样,唯一的区别就是变了顺序,所以总体的递归代码如下:

class Solution {
    public List preorderTraversal(TreeNode root) {
        List result = new ArrayList();
        preorder(root, result);
        return result;
    }

    public void preorder(TreeNode root, List result) {
        if (root == null) {
            return;
        }
        preorder(root.left, result);
        result.add(root.val);   //注意
        preorder(root.right, result);
    }
}

  对于迭代法,难度会更大一点!!!

  中序遍历是左中右,但是代码和上面有一些不同,中序遍历是左中右,先访问的是二叉树顶部的节点,然后一层一层向下访问,直到到达树左面的最底部再开始处理节点(也就是在把节点的数值放进result数组中),这就造成了处理顺序和访问顺序是不一致的。在使用迭代法写中序遍历,就需要借用指针的遍历来帮助访问节点,栈则用来处理节点上的元素。

  所以我们可以写出代码如下:

class Solution {
    public List inorderTraversal(TreeNode root) {
        List result = new ArrayList();
        if (root == null){
            return result;
        }
        Stack stack = new Stack();
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()){
           if (cur != null){
               stack.push(cur);
               cur = cur.left;
           }else{
               cur = stack.pop();
               result.add(cur.val);
               cur = cur.right;
           }
        }
        return result;
    }
}

5.后序遍历

  后序遍历的顺序是左右中,即先左子树、右子树、根节点,那么我们先考虑递归进行求解。

  思路和上面一样,唯一的区别就是变了顺序,所以总体的递归代码如下:

class Solution {
    public List preorderTraversal(TreeNode root) {
        List result = new ArrayList();
        preorder(root, result);
        return result;
    }

    public void preorder(TreeNode root, List result) {
        if (root == null) {
            return;
        }
        preorder(root.left, result);
        preorder(root.right, result);
        result.add(root.val);   //注意
    }
}

  对于迭代法,会前序遍历难度会小一点!!!

  先序遍历是中左右,后续遍历是左右中,那么我们只需要调整一下先序遍历的代码顺序,就变成中右左的遍历顺序,然后在反转result数组,输出的结果顺序就是左右中了,如下图:

    二叉树的遍历插图1

  所以我们可以很快的写出代码如下:

class Solution {
    public List postorderTraversal(TreeNode root) {
        List result = new ArrayList();
        if (root == null){
            return result;
        }
        Stack stack = new Stack();
        stack.push(root);
        while (!stack.isEmpty()){
            TreeNode node = stack.pop();
            result.add(node.val);
            if (node.left != null){
                stack.push(node.left);
            }
            if (node.right != null){
                stack.push(node.right);
            }
        }
        Collections.reverse(result);
        return result;
    }
}

  注意,这里主要是入栈顺序变了,变成先左后右!!!

6.层序遍历

层序遍历一个二叉树。就是从左到右一层一层的去遍历二叉树。这种遍历的方式和我们之前讲过的都不太一样。

需要借用一个辅助数据结构即队列来实现,队列先进先出,符合一层一层遍历的逻辑,而是用栈先进后出适合模拟深度优先遍历也就是递归的逻辑。

了解了思路,我们可以很快的写出层序遍历的代码:

class Solution {
    public List> resList = new ArrayList>();
    public List> levelOrder(TreeNode root) {
        checkFun02(root);
        return resList;
    }
    public void checkFun02(TreeNode node) {
        if (node == null) return;
        Queue que = new LinkedList();
        que.offer(node);
        while (!que.isEmpty()) {
            List itemList = new ArrayList();
            int len = que.size();
            while (len > 0) {
                TreeNode tmpNode = que.poll();
                itemList.add(tmpNode.val);
                if (tmpNode.left != null) que.offer(tmpNode.left);
                if (tmpNode.right != null) que.offer(tmpNode.right);
                len--;
            }
            resList.add(itemList);
        }
    }
}

  主要就是建立一个队列,依次对出队列的数的左右子树入队,同时记录下当前队列的大小,这样可以每一次得到一层的数

  怎么样,看完以后是不是简单多了,当然得有一点点这个方面基础,不然看起来还是有点费劲!!!

 

文章来源于互联网:二叉树的遍历

THE END
分享
二维码