二叉树遍历专题 | 好好学java | Spring Boot | Spring Cloud | 微服务 | Java技术 | Java面试 | 分布式

Java刷题

剑指offer

发布日期: 2021-04-05

作者: 欧阳思海

文章字数: 4.3k

阅读时长: 19 分

阅读次数:

本人花费半年的时间总结的《Java面试指南》已拿腾讯等大厂offer，已开源在github ，欢迎star！

本文GitHub https://github.com/OUYANGSIHAI/JavaInterview 已收录，这是我花了6个月总结的一线大厂Java面试总结，本人已拿大厂offer，欢迎star

原文链接：blog.ouyangsihai.cn >> 二叉树遍历专题

今天来全面学习下二叉树的几种遍历方式，包括前序遍历、中序遍历、后序遍历、层次遍历。定义以下数据结构为二叉树的节点。


public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

// 构建二叉树
public static TreeNode buildBinaryTree() {
    TreeNode[] nodes = new TreeNode[7];
    for (int i = 0; i  nodes.length; i++) {
        nodes[i] = new TreeNode(i + 1);
    }
    nodes[0].setLeft(nodes[1]);
    nodes[0].setRight(nodes[2]);
    nodes[1].setLeft(nodes[3]);
    nodes[1].setRight(nodes[4]);
    nodes[2].setLeft(nodes[5]);
    nodes[2].setRight(nodes[6]);
    return nodes[0];
}

以下二叉树为示例二叉树。

通过不同的遍历方式得到如下结果：
前序遍历：[1, 2, 4, 5, 3, 6, 7]
中序遍历：[4, 2, 5, 1, 6, 3, 7]
后序遍历：[4, 5, 2, 6, 7, 3, 1]
层次遍历：[1, 2, 3, 4, 5, 6, 7]

前序遍历

前序遍历的顺序为：根节点、左子树、右子树。

递归版


public class Solution {

    public ListInteger preOrder(TreeNode root) {
        ListInteger orders = new LinkedList();
        preOrder(root, orders);
        return orders;
    }

    public void preOrder(TreeNode root, ListInteger orders) {
        if (root == null) {
            return;
        }
        // 处理根节点
        orders.add(root.val);
        // 处理左子树
        preOrder(root.left, orders);
        // 处理右子树
        preOrder(root.right, orders);
    }
}

迭代版 1


public class Solution {

    public ListInteger preOrder(TreeNode root) {
        ListInteger orders = new LinkedList();
        // 只存储右子树
        StackTreeNode stack = new Stack();

        while(root != null || !stack.isEmpty()) {
            // 此时stack不为空，弹出右子树
            if (root == null) {
                root = stack.pop();
            }
            // 记录根节点
            orders.add(root.val);
            // 存储右子树
            if (root.right != null) {
                stack.push(root.right);
            }
            // 处理左子树
            root = root.left;
        }
        return orders;
    }
}

迭代版 2


public ListInteger preOrder(TreeNode root) {
    ListInteger orders = new LinkedList();
    // 存储根节点，获取右子树
    StackTreeNode stack = new Stack();
    while(root != null || !stack.isEmpty()) {
        if (root != null) {
            // 记录根节点
            orders.add(root.val);
            // 暂存根节点
            stack.push(root);
            // 处理左子树
            root = root.left;
        } else { // 此时root == null，stack不为空
            root = stack.pop();
            // 处理右子树
            root = root.right;
        }
    }
    return orders;
}

中序遍历

中序遍历的顺序为：左子树、根节点、右子树。

递归版


public class Solution {
    public ListInteger inOrder(TreeNode root) {
        ListInteger orders = new LinkedList();
        inOrder(root, orders);
        return orders;
    }
    public void inOrder(TreeNode root, ListInteger orders) {
        if (root == null) {
            return;
        }
        // 处理左子树
        inOrder(root.left, orders);
        //  处理根节点
        orders.add(root.val);
        // 处理右子树
        inOrder(root.right, orders);
    }
}

迭代版


public ListInteger inOrder(TreeNode root) {
    ListInteger orders = new LinkedList();

    // 存储根节点
    StackTreeNode stack = new Stack();

    while(root != null || !stack.isEmpty()) {
        if (root != null) {
            // 暂存根节点
            stack.push(root);
            // 处理左子树
            root = root.left;
        } else { // 此时root == null，stack不为空
            root = stack.pop();
            // 记录根节点，和前序遍历的唯一不同点
            orders.add(root.val);
            // 处理右子树
            root = root.right;
        }
    }

    return orders;
}

后序遍历

后序遍历的顺序为：左子树、右子树、根节点。

递归版


public class Solution {
    public ListInteger postOrder(TreeNode root) {
        ListInteger orders = new LinkedList();
        postOrder(root, orders);
        return orders;
    }
    public void postOrder(TreeNode root, ListInteger orders) {
        if (root == null) {
            return;
        }
        // 处理左子树
        postOrder(root.left, orders);
        // 处理右子树
        postOrder(root.right, orders);
        //  处理根节点
        orders.add(root.val);
    }
}

迭代版


public ListInteger postOrder(TreeNode root) {
    ListInteger orders = new LinkedList();
    if (root == null) {
        return orders;
    }
    // 存储左右节点
    StackTreeNode stack = new Stack();
    stack.push(root);
    while(!stack.isEmpty()) {
        root = stack.pop();
        // 前插法
        orders.add(0, root.val);
        // 左子树先入栈，后处理
        if (root.left != null) {
            stack.push(root.left);
        }
        // 右子树先入栈，先处理
        if (root.right != null) {
            stack.push(root.right);
        }
    }
    return orders;
}

层次遍历


public ListInteger levelOrder(TreeNode root) {
    ListInteger orders = new LinkedList();
    if (root == null) {
        return orders;
    }
    // 队列，先左子树、后右子树
    ListTreeNode queue = new LinkedList();
    queue.add(root);

    while(!queue.isEmpty()) {
        // 处理第一个元数据
        root = queue.remove(0);
        orders.add(root.val);
        // 左子树先入栈，先处理
        if (root.left != null) {
            queue.add(root.left);
        }
        // 右子树后入栈，后处理
        if (root.right != null) {
            queue.add(root.right);
        }
    }

    return orders;
}

下面来做一些练习。

105. 从前序与中序遍历序列构造二叉树

本题来自 LeetCode：105. 从前序与中序遍历序列构造二叉树^[1]

题目详情

根据一棵树的前序遍历与中序遍历构造二叉树。
注意：你可以假设树中没有重复的元素。
例如，给出


前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]

返回如下的二叉树：

题目分析

前序遍历数组的组成为`根节点 + 连续的左子树 + 连续的右子树`

中序遍历数组的组成为`连续的左子树 + 根节点 + 连续的右子树`

前序遍历数组的第一个值就是根节点，由于无重复数字，因此可在中序遍历数组中找到根节点的位置，就可以知道左子树节点的个数，这样就能把两个数组的左右树的范围切分开；

题目解答

解法一


class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTree(preorder, 0, preorder.length - 1,
            inorder, 0, inorder.length - 1);
    }
    public TreeNode buildTree(int[] preorder, int preLeft, int preRight,
                              int[] inorder, int inLeft, int inRight) {
        // 中止条件
        if(preLeft  preRight) {
            return null;
        }

        //  前序的第一个节点就是根节点
        int rootValue = preorder[preLeft];
        TreeNode root = new TreeNode(rootValue);

        // 从 中序遍历中找到根节点的位置， step为左子树所有节点的个数
        int step = 0;
        while(inorder[inLeft + step] != rootValue) {
            step ++;
        }
        // 处理左子树，由上可知，左子树的节点个数为step
        // 前序遍历数组，排除根节点preorder[preLeft], 左子树的范围为[preLeft+1, preLeft+step]
        // 前序遍历数组，排除根节点inorder[inLeft + step], 左子树的范围为[inLeft, inLeft+step-1]
        root.left = buildTree(preorder, preLeft + 1, preLeft + step,
                              inorder, inLeft, inLeft + step - 1);

        // 处理右子树
        // 前序遍历数组，排除左子树的范围, 右子树的范围为[preLeft+step+1, preRight]
        // 前序遍历数组，排除左子树的范围, 右子树的范围为[inLeft+step+1, inRight]
        root.right = buildTree(preorder, preLeft + step + 1, preRight,
                               inorder, inLeft + step + 1, inRight);
        return root;
    }
}

复杂度分析：
时间复杂度：O(n ^ 2)，中间查找中序数组中根节点时间复杂度为O(n)，每次递归都会创建一个节点，复杂度为O(n)，所以总复杂度为O(n ^ 2)
空间复杂度：O(n)，递归调用栈

解法二

注意到，查找中序数组根节点这一步其实只需要知道根节点的位置，因此可以有哈希表缓存起来，可以将时间复杂度降到O(n)。


/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        MapInteger, Integer indexTable = new HashMap(inorder.length);
        // 记录中序遍历每个节点的位置，空间换时间
        for(int i = 0; i  inorder.length; i ++) {
            indexTable.put(inorder[i], i);
        }
        return buildTree(preorder, 0, preorder.length - 1,
            inorder, 0, inorder.length - 1, indexTable);
    }
    public TreeNode buildTree(int[] preorder, int preLeft, int preRight,
                              int[] inorder, int inLeft, int inRight,
                              MapInteger, Integer indexTable) {
        if(preLeft  preRight) {
            return null;
        }
        int rootValue = preorder[preLeft];
        TreeNode root = new TreeNode(rootValue);

        // 从 中序遍历中找到根节点的位置， step为左子树所有节点的个数
        int step =  indexTable.get(rootValue) - inLeft;

        root.left = buildTree(preorder, preLeft + 1, preLeft + step,
                              inorder, inLeft, inLeft + step - 1,
                              indexTable);
        root.right = buildTree(preorder, preLeft + step + 1, preRight,
                               inorder, inLeft + step + 1, inRight,
                               indexTable);
        return root;
    }
}

复杂度分析：
时间复杂度：O(n)，每次递归都会创建一个节点，复杂度为O(n)空间复杂度：O(n)，递归调用栈和缓存表

106. 从中序与后序遍历序列构造二叉树

本题来自 LeetCode：106. 从中序与后序遍历序列构造二叉树^[2]

题目详情

根据一棵树的中序遍历与后序遍历构造二叉树。
注意: 你可以假设树中没有重复的元素。
例如，给出
中序遍历inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]
返回如下的二叉树：

题目分析

和上题同样的套路：

后序遍历数组的组成为`连续的左子树 + 连续的右子树 + 根节点`

中序遍历数组的组成为`连续的左子树 + 根节点 + 连续的右子树`

后序遍历数组的最后值就是根节点，由于无重复数字，因此可在中序遍历数组中找到根节点的位置，就可以知道左子树节点的个数，这样就能把两个数组的左右树的范围切分开；

题目解答

解法一


class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        return buildTree(postorder, 0, postorder.length - 1,
            inorder, 0, inorder.length - 1);
    }
    public TreeNode buildTree(int[] postorder, int postLeft, int postRight,
                              int[] inorder, int inLeft, int inRight) {
        // 中止条件
        if(postLeft  postRight) {
            return null;
        }

        //  后序的最后个节点就是根节点
        int rootValue = postorder[postRight];
        TreeNode root = new TreeNode(rootValue);

        // 从 中序遍历中找到根节点的位置， step为左子树所有节点的个数
        int step = 0;
        while(inorder[inLeft + step] != rootValue) {
            step ++;
        }

        // 处理左子树，由上可知，左子树的节点个数为step
        // 后序遍历数组，左子树的范围为[postLeft + 0, postLeft + step-1]
        // 中序遍历数组，排除根节点inorder[inLeft + step], 左子树的范围为[inLeft + 0, inLeft + step-1]
        root.left = buildTree(postorder, postLeft, postLeft + step - 1,
            inorder, inLeft, inLeft + step - 1);

        // 处理右子树，由上可知，左子树的节点个数为step
        // 后序遍历数组，排除左子树的范围与根节点postorder[postRight], 右子树的范围为[preLeft+step, preRight - 1]
        // 中序遍历数组，排除左子树的范围, 右子树的范围为[inLeft+step+1, inRight]
        root.right = buildTree(postorder, postLeft + step, postRight - 1,
            inorder, inLeft + step + 1, inRight);

        return root;
    }
}

解法二

注意到，查找中序数组根节点这一步其实只需要知道根节点的位置，因此可以有哈希表缓存起来，可以将时间复杂度降到O(n)。


class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        MapInteger, Integer indexTable = new HashMap(inorder.length);
        // 记录中序遍历每个节点的位置，空间换时间
        for(int i = 0; i  inorder.length; i ++) {
            indexTable.put(inorder[i], i);
        }
        return buildTree(postorder, 0, postorder.length - 1,
            inorder, 0, inorder.length - 1, indexTable);
    }
    public TreeNode buildTree(int[] postorder, int postLeft, int postRight,
                              int[] inorder, int inLeft, int inRight,
                              MapInteger, Integer indexTable) {
        if(postLeft  postRight) {
            return null;
        }
        int rootValue = postorder[postRight];
        TreeNode root = new TreeNode(rootValue);

        // 从 中序遍历中找到根节点的位置， step为左子树所有节点的个数
        int step = indexTable.get(rootValue) - inLeft;

        root.left = buildTree(postorder, postLeft, postLeft + step - 1,
            inorder, inLeft, inLeft + step - 1, indexTable);
        root.right = buildTree(postorder, postLeft + step, postRight - 1,
            inorder, inLeft + step + 1, inRight, indexTable);
        return root;
    }
}

复杂度分析：
时间复杂度：O(n)，每次递归都会创建一个节点，复杂度为O(n)空间复杂度：O(n)，递归调用栈和缓存表

102. 二叉树的层次遍历

本题来自 LeetCode：102. 二叉树的层次遍历^[3]

题目详情

给定一个二叉树，返回其按层次遍历的节点值。（即逐层地，从左到右访问所有节点）。
例如:
给定二叉树:[3,9,20,null,null,15,7],

返回其层次遍历结果：


[
  [3],
  [9,20],
  [15,7]
]

题目解答


/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListListInteger levelOrder(TreeNode root) {
        ListListInteger levels = new ArrayList();
        if(root == null) {
            return levels;
        }
        ListTreeNode queue = new LinkedList();
        // 根节点入队
        queue.add(root);
        while(!queue.isEmpty()) {
            // 记录当前层的节点个数
            int size = queue.size();
            // 存储当前层的节点
            ListInteger level = new ArrayList();
            // 依次处理当前层（前size个）节点
            for(int i = 0; i  size; i ++) {
                TreeNode node = queue.remove(0);
                level.add(node.val);
                // 左子树入队
                if(node.left != null) {
                    queue.add(node.left);
                }
                // 右子树入队
                if(node.right != null) {
                    queue.add(node.right);
                }
            }
            // 当前层节点列表入队
            levels.add(level);
        }
        return levels;
    }
}

复杂度分析：
时间复杂度：O(n)
空间复杂度：O(n)

107. 二叉树的层次遍历 II

本题来自 LeetCode：107. 二叉树的层次遍历 II^[4]

题目详情

给定一个二叉树，返回其节点值自底向上的层次遍历。（即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
例如：
给定二叉树[3,9,20,null,null,15,7],

返回其自底向上的层次遍历为：


[
  [15,7],
  [9,20],
  [3]
]

题目分析

和102. 二叉树的层次遍历唯一不同点在当前层节点列表入队时，采用头插法。

题目解答


/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListListInteger levelOrderBottom(TreeNode root) {
         ListListInteger levels = new ArrayList();
        if(root == null) {
            return levels;
        }
        ListTreeNode queue = new LinkedList();
        // 根节点入队
        queue.add(root);
        while(!queue.isEmpty()) {
            // 记录当前层的节点个数
            int size = queue.size();
            // 存储当前层的节点
            ListInteger level = new ArrayList();
            // 依次处理当前层（前size个）节点
            for(int i = 0; i  size; i ++) {
                TreeNode node = queue.remove(0);
                level.add(node.val);
                // 左子树入队
                if(node.left != null) {
                    queue.add(node.left);
                }
                // 右子树入队
                if(node.right != null) {
                    queue.add(node.right);
                }
            }
            // 当前层节点列表入队，和自上而下唯一不同点
            levels.add(0, level);
        }
        return levels;
    }
}

复杂度分析：
时间复杂度：O(n)
空间复杂度：O(n)

637. 二叉树的层平均值

本题来自 LeetCode：637. 二叉树的层平均值^[5]

题目详情

给定一个非空二叉树, 返回一个由每层节点平均值组成的数组.
示例 1:


输入:
    3
   / 
  9  20
    /  
   15   7

输出: `[3, 14.5, 11]`
解释:
第0层的平均值是 3,  第1层是 14.5, 第2层是 11. 因此返回 [3, 14.5, 11].

注意：节点值的范围在 32 位有符号整数范围内。

题目分析

和102. 二叉树的层次遍历类似。

题目解答


/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListDouble averageOfLevels(TreeNode root) {
        ListDouble averages = new ArrayList();
        if(root == null) {
            return averages;
        }
        ListTreeNode queue = new LinkedList();
        // 根节点入队
        queue.add(root);
        while(!queue.isEmpty()) {
            // 记录当前层的节点个数
            int size = queue.size();
            // 记录当前层节点的和
            long sum = 0l;
            // 依次处理当前层（前size个）节点
            for(int i = 0; i  size; i ++) {
                TreeNode node = queue.remove(0);
                sum += node.val;
                // 左子树入队
                if(node.left != null) {
                    queue.add(node.left);
                }
                // 右子树入队
                if(node.right != null) {
                    queue.add(node.right);
                }
            }
            // 当前层节点列表入队
            averages.add(sum / (size * 1.0));
        }
        return averages;
    }
}

复杂度分析：
时间复杂度：O(n)
空间复杂度：O(n)

429. N 叉树的层序遍历

本题来自 LeetCode：429. N 叉树的层序遍历^[6]

题目详情

给定一个 N 叉树，返回其节点值的层序遍历。(即从左到右，逐层遍历)。
例如，给定一个 3 叉树 :

返回其层序遍历:


[
     [1],
     [3,2,4],
     [5,6]
]

题目分析

和二叉树的层次遍历类似。

题目解答


/*
// Definition for a Node.
class Node {
    public int val;
    public ListNode children;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, ListNode _children) {
        val = _val;
        children = _children;
    }
};
*/
class Solution {
    public ListListInteger levelOrder(Node root) {
        ListListInteger levels = new ArrayList();
        if(root == null) {
            return levels;
        }
        ListNode queue = new LinkedList();
        // 根节点入队
        queue.add(root);
        while(!queue.isEmpty()) {
            // 记录当前层的节点个数
            int size = queue.size();
            // 存储当前层的节点
            ListInteger level = new ArrayList();
            // 依次处理当前层（前size个）节点
            for(int i = 0; i  size; i ++) {
                Node node = queue.remove(0);
                level.add(node.val);
                // 子树入队
                if(node.children != null && !node.children.isEmpty()) {
                    queue.addAll(node.children);
                }
            }
            // 当前层节点列表入队
            levels.add(level);
        }
        return levels;
    }
}

复杂度分析：
时间复杂度：O(n)
空间复杂度：O(n)

103. 二叉树的锯齿形层次遍历

本题来自 LeetCode：103. 二叉树的锯齿形层次遍历^[7]

题目详情

给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

例如：给定二叉树[3,9,20,null,null,15,7],

返回锯齿形层次遍历如下：


[
  [3],
  [20,9],
  [15,7]
]

题目分析

和二叉树的层次遍历类似。但需要记录当前层是奇数层还是偶数层，当前层列表，奇数层采用尾插发，偶数层采用头插法。

题目解答


/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListListInteger zigzagLevelOrder(TreeNode root) {
        ListListInteger levels = new ArrayList();
        if(root == null) {
            return levels;
        }
        ListTreeNode queue = new LinkedList();
        // 根节点入队
        queue.add(root);
        boolean even = true;
        while(!queue.isEmpty()) {
            even = !even;
            // 记录当前层的节点个数
            int size = queue.size();
            // 存储当前层的节点
            ListInteger level = new ArrayList();
            // 依次处理当前层（前size个）节点
            for(int i = 0; i  size; i ++) {
                TreeNode node = queue.remove(0);
                if(even) {
                    level.add(0, node.val);
                } else {
                    level.add(node.val);
                }

                // 左子树入队
                if(node.left != null) {
                    queue.add(node.left);
                }
                // 右子树入队
                if(node.right != null) {
                    queue.add(node.right);
                }
            }
            // 当前层节点列表入队
            levels.add(level);
        }
        return levels;
    }
}