二叉树的递归与非递归遍历


前言

跟着感觉走


一、二叉树

二叉树的递归遍历其实就相当于DFS,这也是为什么在递归遍历中,会使用到

层序遍历相当于图论中的BFS,BFS使用的队列来实现,这也决定了层序遍历是使用队列来实现的

在这里插入图片描述
public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
}

二、递归遍历

1.先序遍历

在这里插入图片描述

输出顺序:A B D E C F

  1. 访问根节点
  2. 遍历左子树
  3. 遍历右子树

实现

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> ans= new ArrayList<Integer>();
        preorder(root, ans);
        return ans;
    }

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

2.中序遍历

在这里插入图片描述

输出顺序: D B E A C F

  1. 遍历左子树
  2. 访问根节点
  3. 遍历右子树

实现

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        inorder(root, ans);
        return ans;
    }

    void inorder(TreeNode root, List<Integer> ans) {
        if (root == null) {
            return;
        }
        inorder(root.left, ans);
        ans.add(root.val);            
        inorder(root.right, ans);
    }
}

3.后序遍历

在这里插入图片描述

输出顺序:D E B A C F

  1. 遍历左子树
  2. 遍历右子树
  3. 访问根节点

实现

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> ans= new ArrayList<>();
        postorder(root, ans);
        return ans;
    }

    void postorder(TreeNode root, List<Integer> ans) {
        if (root == null) {
            return;
        }
        postorder(root.left, ans);
        postorder(root.right, ans);
        ans.add(root.val);           
    }
}

三、非递归遍历

1、非递归先序遍历

步骤

  1. 先压入根节点,在弹出根节点
  2. 依次压入根节点的右子节点和左子节点
  3. 弹出左子节点
  4. 在压入弹出的左子节点的右子节点(此时弹出的左子节点为新的根节点,继续执行1-4,直至为null)

在入栈的过程中,应该先把一个树的右节点先加入栈中,随后再加入左节点。
这是因为在栈的思想中是先进后出,后把左节点放入,这样在弹出的时候才会先弹出左节点。
队列来代替栈就属于层次遍历

实现

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> ans= new ArrayList<>();
        if (root == null){
            return ans;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);                    //根节点入栈
        while (!stack.isEmpty()){            //如果栈不为空
            TreeNode node = stack.pop();     //弹出根节点(2.此时的根节点为栈顶的左子节点)
            ans.add(node.val);               //弹出的根节点放入集合
            if (node.right != null){         //压入根节点的右子节点
                stack.push(node.right);
            }
            if (node.left != null){          //压入根节点的左子节点
                stack.push(node.left);
            }
        }
        return ans;
    }
}

2.非递归后序遍历

步骤

  1. 先压入根节点,在弹出根节点
  2. 依次压入根节点的左子节点和右子节点
  3. 弹出右子节点
  4. 在压入弹出的右子节点的左子节点(此时弹出的右子节点为新的根节点,继续执行1-4,直至为null)
  5. 反转数组

非递归后序遍历代码和非递归前序遍历代码十分相似,最后的反转数组才是神来之笔

实现

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        if (root == null){
            return ans;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()){
            TreeNode node = stack.pop();
            ans.add(node.val);
            if (node.left != null){
                stack.push(node.left);
            }
            if (node.right != null){
                stack.push(node.right);
            }
        }
        Collections.reverse(result);     //反转数组
        return ans;
    }
}

2.非递归中序遍历

步骤

中序遍历中,遍历的顺序和处理的顺序是不一样的,用指针遍历节点,用栈记录遍历过的节点。
对于任一结点,优先访问其左孩子,而左孩子结点又可以看做一个根结点,然后继续访问其左孩子结点,使其入栈。直到遇到左孩子结点为空的结点才进行访问,然后按相同的规则访问其右子树。

左孩子为空则弹出自己,右孩子为空则继续弹出

实现

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> ans= new ArrayList<>();  //集合,用于返回元素
        if (root == null){
            return ans;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;                      //初始化指针指向根节点
        while (cur != null || !stack.isEmpty()){  //如果指针为null或栈为空则结束
           if (cur != null){
               stack.push(cur);                   //当前根节点入栈
               cur = cur.left;                    //更新指针为入栈根节点的左子节点
           }else{                                 //左子节点为null
               cur = stack.pop();                 //出栈
               ans.add(cur.val);                  //将当前节点的值加入集合
               cur = cur.right;                   //更新指针为入栈根节点的右子节点
           }
        }
        return ans;
    }
}

四、层序遍历

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();   //二维数组
        Queue<TreeNode> queue = new LinkedList<>();
        if(root!=null){
            //第一个结点加入队列
            queue.offer(root);
        }
        while(!queue.isEmpty()){
            int size = queue.size();
            List<Integer> temp = new ArrayList<>();
            while(size-- >0){
                TreeNode node=queue.peek();
                queue.remove();
                temp.add(node.val);
                if(node.left != null){
                    queue.offer(node.left);
                }
                if(node.right != null){
                    queue.offer(node.right);
                }
            }    //一层结束
            res.add(temp);
        }
        return res;
    }
}
消息盒子
# 您需要首次评论以获取消息 #
# 您需要首次评论以获取消息 #

只显示最新10条未读和已读信息