【二叉树遍历 Java版】二叉树的前中后序遍历and层次遍历

最新推荐文章于 2025-04-14 22:26:17 发布

PleaseBrave

最新推荐文章于 2025-04-14 22:26:17 发布

阅读量820

点赞数 16

分类专栏：力扣刷题文章标签：数据结构与算法二叉树二叉树的遍历 bfs dfs

本文链接：https://blog.csdn.net/massive_jiang/article/details/143405251

版权

力扣刷题专栏收录该内容

34 篇文章

订阅专栏

二叉树的前中后序遍历and层次遍历

深度优先遍历
广度优先遍历

深度优先遍历

深度优先遍历中，根据左右孩子节点和父节点的访问顺序，分为了前、中、后序遍历。这里的前中后是指父节点相对左右孩子节点的位置：前序遍历即父-左-右，中序遍历即左-父-右，后序遍历即左-右-父。
下面一个例子：
在这里插入图片描述
所谓深度遍历，即一个节点下面有子树的话，先遍历左子树（如果有）再遍历右子树（如果有），子树遍历完了，加上这个节点（根据前中后序遍历实际情况考虑这个节点是什么时候访问），这棵树遍历完了，再往上走，回到其父节点……以此类推。

题目链接

144. 二叉树的前序遍历
 94. 二叉树的中序遍历
 145. 二叉树的后序遍历

递归

递归的代码非常简洁，一个函数自己调用自己，加上一个递归结束条件，即可。
前中后序的递归结束条件都是当前节点node为空。注意，这里递归函数不需要返回值。

前序遍历

遇到一个节点，就遍历它，然后遍历左子树，然后遍历右子树，这就是前序遍历的顺序。

class Solution {
    static List<Integer> ans;
    public List<Integer> preorderTraversal(TreeNode root) {
        ans = new ArrayList<>();
        getNode(root);
        return ans;
    }
    public static void getNode(TreeNode root){
        if(root == null)
            return;
        ans.add(root.val); // 遍历节点
        getNode(root.left); // 遍历左子树
        getNode(root.right); // 遍历右子树
    }
}

中序遍历

遇到一个节点，先遍历其左子树，左子树遍历完了，再遍历这个节点，然后再遍历这个树的右子树，这就是中序遍历的顺序。

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

    public static void getNode(TreeNode root, List<Integer> ans){
        if(root == null)
            return;
        getNode(root.left,ans); // 先遍历左子树
        ans.add(root.val); // 再遍历当前节点
        getNode(root.right,ans); // 再遍历右子树
    }
}

后序遍历

后序遍历是左-右-中，即先遍历左子树、右子树，最后再遍历当前节点。

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<Integer>();
        getNode(root, ans);
        return ans;
    }
    public static void getNode(TreeNode root, List<Integer> ans){
        if(root == null)
            return;
        getNode(root.left,ans); // 遍历左子树      
        getNode(root.right,ans); // 遍历右子树
        ans.add(root.val);  // 遍历当前节点
    }
}

这里有个很有意思的点，前序遍历是中-左-右，前序遍历的过程中，如果交换左右子树的遍历顺序，变成中-右-左，然后再reverse反转一下，变成左-右-中，即为后序遍历了。
树的遍历（整体）是子树遍历（局部）组成的，最后整体反转，局部内也是反转的，即子树也是满足左-右-中的。

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<Integer>();
        getNode(root, ans);
        Collections.reverse(ans); // 反转
        return ans;
    }

    public static void getNode(TreeNode root, List<Integer> ans){
        if(root == null)
            return;                 
        ans.add(root.val); // 遍历当前节点
        getNode(root.right,ans); // 遍历右子树
        getNode(root.left,ans);  // 遍历左子树
    }
}

迭代

所有递归调用的方法，都能转化成非递归版本，一般使用栈来保存中间状态遍历。在树的遍历中即用栈保存，在路径上但是还没有访问的节点。

前序遍历

前序遍历是遇到一个节点就访问，然后呢？然后再遍历子树，左子树和右子树，在迭代版本中，就要保存左节点和右节点。注意我们用的栈，栈是先入后出，后入先出，我们要先遍历左子树，那么就要后入栈。栈不空就表示还有节点没有访问。

class Solution {    
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        Stack<TreeNode> tree = new Stack<>();
        if(root == null)
            return ans;
        tree.push(root);
        while(!tree.empty()){
            TreeNode node = tree.pop();
            ans.add(node.val); // 访问当前节点
            if(node.right != null)  // 右孩子先入栈，后出栈
                tree.push(node.right);
            if(node.left != null)   // 左孩子后入栈，先出栈
                tree.push(node.left);
        }
        return ans;
    }    
}

后序遍历

前面提到，前序遍历中，左右子树遍历的顺序交换，遍历结果整体反转就能得到得到后序遍历的结果。

//遍历顺序类似前序，得到 中-右-左， 反转即可得到 左-右-中
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<Integer>();
        if(root == null)
            return ans;
        Stack<TreeNode> tree = new Stack<>();
        tree.push(root);
        while(!tree.empty()){
            TreeNode node = tree.pop();
            ans.add(node.val); // 访问当前节点
            if(node.left != null) // 左孩子先入栈，后访问
                tree.push(node.left);
            if(node.right != null) // 右孩子后入栈，先访问
                tree.push(node.right);
        }
        Collections.reverse(ans); // 反转
        return ans;
    }
}

中序遍历

中序遍历第一个节点是什么？是整棵树最左边的孩子节点，或者整棵树最左边的没有左孩子的节点。那么就意味着，在找到这个节点之前，路上遇到的节点都要保存起来。且先保存的全是整棵树的左边部分，访问完了根节点的时候，右边节点还没入栈呢~ 因此不能单纯用栈非空为遍历结束的条件。同时用一个当前阶段node来记录是否遍历结束。

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<Integer>();
        if(root == null)
            return ans;
        Stack<TreeNode> tree = new Stack<>();
        tree.push(root);
        TreeNode node = root.left; // 看左孩子
        while(node != null ||!tree.empty()){
        	// 一直向下，直到没有左孩子，才能遍历这个节点
            if(node != null){
                tree.push(node);// 路过的节点都入栈保存
                node = node.left;
            }else{
                node = tree.pop();
                ans.add(node.val); // 访问当前节点
                node = node.right; // 再访问右子树
            }
        }
        return ans;
    }   
}

统一迭代

上面迭代版本中，前序和后序代码很相似，但是中序非常不一样，还需要用node是否为空辅助判断遍历是否结束。如果有一个前中后序统一的代码模板，会更方便记忆。
现在不管当前节点是否要访问，都把它放入栈里面，但是依旧要保持前中后序遍历中节点的顺序。即前序：先存右孩子、再存左孩子、再存自己；中序：先存右孩子、再存自己、再存左孩子；后序：先存自己、再存右孩子、再存左孩子。因为入栈是先入后出，所有存的顺序是和遍历顺序相反的。
然后在当前节点后面存一个null，下次碰到null就知道下一个节点应该访问了。

前序遍历

入栈顺序是右-左-中-null

class Solution {    
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        Stack<TreeNode> tree = new Stack<>();
        if(root == null)
            return ans;
        tree.push(root);
        while(!tree.empty()){
            TreeNode node = tree.pop(); // 栈顶节点出栈
            if(node != null){ // 不为空考虑左右孩子入栈     
                if(node.right != null)  // 右孩子先入栈，后出栈
                    tree.push(node.right);
                if(node.left != null)   // 左孩子后入栈，先出栈
                    tree.push(node.left);                
                tree.push(node); // 当前节点再入栈
                tree.push(null); // null标记当前节点
            }else{ // 栈顶是null说明前面一个就是要访问的
                node = tree.pop();
                ans.add(node.val);// 访问
            }           
        }
        return ans;
    }    
}

后序遍历

入栈顺序是中-null-右-左

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<Integer>();
        if(root == null)
            return ans;
        Stack<TreeNode> tree = new Stack<>();
        tree.push(root);
        while(!tree.empty()){
            TreeNode node = tree.peek(); //注意当前节点不出栈
            if(node != null){
                tree.push(null);// 添加标志null节点
                if(node.right != null)
                    tree.push(node.right);
                if(node.left != null)
                    tree.push(node.left);                
            }else{
                tree.pop();
                node = tree.pop(); // 访问当前节点
                ans.add(node.val);
            }
        }
        return ans;
    }
}

中序遍历

入栈顺序是右-中-null-左

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<Integer>();
        if(root == null)
            return ans;
        Stack<TreeNode> tree = new Stack<>();
        tree.push(root);
        while(!tree.empty()){
            TreeNode node = tree.pop();
            if(node != null){
                if(node.right != null) // 右孩子先入栈
                    tree.push(node.right);
                tree.push(node); // 当前节点入栈
                tree.push(null); // 添加标识
                
                if(node.left != null) // 左孩子入栈
                    tree.push(node.left);
            }else{
                node = tree.pop();
                ans.add(node.val);// 访问节点
            }
        }
        return ans;
    }   
}

广度优先遍历

广度优先遍历即为层次遍历。深度用栈，广度用队列，先入先出。
每一层的节点数量，为当前queue中元素的数量！

102. 二叉树的层序遍历

class Solution {
    public List<List<Integer>> ans = new ArrayList<List<Integer>>();
    public List<List<Integer>> levelOrder(TreeNode root) {
        if(root == null)
            return ans;
        Deque<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        while(!queue.isEmpty()){
            List<Integer> levelElements = new ArrayList<Integer>();
            int levelSize = queue.size(); //当前层的节点数量
            for(int i=0;i<levelSize;i++){
                TreeNode node = queue.poll();
                levelElements.add(node.val);
                // 出队后左右孩子依次入队
                if(node.left!= null)
                    queue.offer(node.left);
                if(node.right!= null)
                    queue.offer(node.right);
            }
            // 从上往下访问 直接将层的结果加入ans中
            ans.add(levelElements);
        }
        return ans;
    }
}

107. 二叉树的层序遍历 II

107. 二叉树的层序遍历 II
这个题目只是从最后一层输出，实际遍历的时候还是从上往下，只是每次把访问的那一层放在最前面。


class Solution {
    public List<List<Integer>> ans = new ArrayList<List<Integer>>();
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        if(root == null)
            return ans;
        Deque<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        while(!queue.isEmpty()){
            List<Integer> levelElements = new ArrayList<Integer>();
            int levelSize = queue.size();
            for(int i=0;i<levelSize;i++){
                TreeNode node = queue.poll();
                levelElements.add(node.val);
                if(node.left!= null)
                    queue.offer(node.left);
                if(node.right!= null)
                    queue.offer(node.right);
            }
            // ❗注意要求从最后一层访问，实际还是从上往下访问，但是每一层的结果都加在最前面
            ans.add(0,levelElements);
        }
        return ans;
    }
}

637. 二叉树的层平均值

637. 二叉树的层平均值

只需要在层次访问的基础上，将各个节点的val求平均。

class Solution {
    public List<Double> ans = new ArrayList<Double>();

    public List<Double> averageOfLevels(TreeNode root) {
        if (root == null)
            return ans;
        Deque<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            TreeNode node = null;
            double sum = 0.0;
            for (int i = 0; i < size; i++) {
                node = queue.poll();
                if (node.left != null)
                    queue.offer(node.left);
                if (node.right != null)
                    queue.offer(node.right);
                // ❗求节点值的和
                sum += node.val;
            }
            // 将平均值加入ans
            ans.add(sum / size);
        }
        return ans;        
    }
}

199. 二叉树的右视图

199. 二叉树的右视图
从广度优先（即层次遍历）的角度，这个题就是访问每一层时，只将这个层最后一个元素放入ans中。因此一个二叉树的右视图，看到的就是每一层最右边的元素。

class Solution {
    public List<Integer> ans = new ArrayList<Integer>();
    public List<Integer> rightSideView(TreeNode root) {
        if(root ==  null)
            return ans;
        Deque<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        while(!queue.isEmpty()){
            int size = queue.size();
            TreeNode node = null;
            while(size > 0){
                node = queue.poll();
                if(node.left != null)
                    queue.offer(node.left);
                if(node.right != null)
                    queue.offer(node.right);
                // ❗只访问最后一个元素
                if(size == 1)
                    ans.add(node.val);
                size--;
            } 
        }
        return ans;        
    }
}