树：熟练手写树的四种遍历方式

树的四种遍历方式

树也是一种用来提高查询效率的数据结构（和哈希表类似）。例如MySQL中的索引就可以基于B+树或者哈希表构建，MongoDB用B树（也称为B-树）来实现索引。

很多关于树的面试题其实都不难，基本上是基于树的四种遍历方式来实现的，所以熟练手写树的四种遍历方式非常重要

我们先说前中后序这三种遍历方式

前序遍历：根，左，右 中序遍历：左，根，右 后序遍历：左，右，根

发现规律没？左右的位置始终不变，前序遍历，根在前面，中序遍历，根在中间，后序遍历根在最后。

前序遍历：A B C D E F
中序遍历：C B D A E F 后序遍历：C D B F E A

层级遍历：A B E C D F

假设树节点定义如下，我们来写一下树的遍历方式

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;
    }
}

list 为一个列表

// 前序遍历
public void traverse(TreeNode root) {
    if (root == null) {
        return;
    }
    list.add(root.val);
    traverse(root.left);
    traverse(root.right);
}

// 中序遍历
public void traverse(TreeNode root) {
    if (root == null) {
        return;
    }
    traverse(root.left);
    list.add(root.val);
    traverse(root.right);
}

// 后序遍历
public void traverse(TreeNode root) {
    if (root == null) {
        return;
    }
    traverse(root.left);
    traverse(root.right);
    list.add(root.val);
}

三种遍历方式的区别只是对root节点做操作的时机不同

// 层次遍历
public void traverse(TreeNode root) {
    Queue<TreeNode> queue = new ArrayDeque<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        list.add(node.val);
        if (node.left != null) {
            queue.add(node.left);
        }
        if (node.right != null) {
            queue.add(node.right);
        }
    }
}

从代码中可以看到前中后序遍历是对树做dfs操作，而树的层次遍历就是对树做bfs操作，就一个bfs模版代码。

二叉树的层平均值

题目地址：LeetCode 637. 二叉树的层平均值

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

示例 1：

输入：
    3
   / \
  9  20
    /  \
   15   7
输出：[3, 14.5, 11]
解释：
第 0 层的平均值是 3 ,  第1层是 14.5 , 第2层是 11 。因此返回 [3, 14.5, 11] 。

树层次遍历的简单变形

public List<Double> averageOfLevels(TreeNode root) {
    List<Double> result = new ArrayList<>();
    if (root == null) {
        return result;
    }
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        double sum = 0;
        int count = queue.size();
        for (int i = 0; i < count; i++) {
            TreeNode treeNode = queue.poll();
            sum += treeNode.val;
            if (treeNode.left != null) {
                queue.add(treeNode.left);
            }
            if (treeNode.right != null) {
                queue.add(treeNode.right);
            }
        }
        result.add(sum / count);
    }
    return result;
}

对称二叉树

题目地址：LeetCode 101. 对称二叉树

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

    1
   / \
  2   2
 / \ / \
3  4 4  3

public boolean isSymmetric(TreeNode root) {
    return judge(root.left, root.right);
}

public boolean judge(TreeNode left, TreeNode right) {
    if (left == null && right == null) {
        return true;
    }
    if (left == null || right == null) {
        return false;
    }
    if (left.val != right.val) {
        return false;
    }
    // 2边和2边比，中间和中间比
    return judge(left.left, right.right) && judge(left.right, right.left);
}

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

题目地址：LeetCode 105. 从前序与中序遍历序列构造二叉树 题目描述： 题目保证： preorder 和 inorder 均 无重复 元素

前序遍历：根 左 右 中序遍历：左 根 右

1. 前序遍历的第一个点为根节点
2. 根据根节点确定根在中序遍历的位置
3. 有了位置就能确定左字数的节点树和右字数的节点树
4. 通过节点数就能确定左子树的前序遍历和中序遍历，然后从第一步递归

public TreeNode buildTree(int[] preorder, int[] inorder) {
    if (preorder.length == 0 || inorder.length == 0) {
        return null;
    }
    TreeNode treeNode = new TreeNode(preorder[0]);
    for (int i = 0; i < inorder.length; i++) {
        if (inorder[i] == preorder[0]) {
            // 左子树前序遍历的结果
            int[] preOrderLeft = Arrays.copyOfRange(preorder, 1, i + 1);
            // 右子树中序遍历的结果
            int[] preOrderRight = Arrays.copyOfRange(preorder, i + 1, preorder.length);
            // 左子树中序遍历的结果
            int[] inOrderLeft = Arrays.copyOfRange(inorder, 0, i);
            // 右子树中序遍历的结果
            int[] inOrderRight = Arrays.copyOfRange(inorder, i + 1, inorder.length);
            // 构建左子树
            treeNode.left = buildTree(preOrderLeft, inOrderLeft);
            // 构建右子树
            treeNode.right = buildTree(preOrderRight, inOrderRight);
        }
    }
    return treeNode;
}