本篇概要

二叉树是大厂面试的常考题之一。面试者除了日常刷题以外，还需要思考二叉树的定义、生成和输出，以便于在面试官提出不同要求时应对自如。每个二叉树的题目基本上都有递归和迭代两种方式，对于简单题来说，建议面试者两种方法都掌握，对于其他难度的题目，建议面试者量力而行。

二叉树的遍历

提升：在本地编译器跑起来，并思考如何将返回值改为void。

    1. 二叉树的前序遍历
    1. 二叉树的中序遍历
    1. 二叉树的后序遍历
  4. 剑指 Offer 33. 二叉搜索树的后序遍历序列：输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。
  5. 剑指 Offer 32 - I. 从上到下打印二叉树：自上而下，自左而右，不分层输出
  6. 剑指 Offer 32 - II. 从上到下打印二叉树 II和 102. 二叉树的层序遍历：自上而下，自左而右，分层输出
    1. 二叉树的层次遍历 II：自下而上，自左而右，分层输出
  8. 剑指 Offer 32 - III. 从上到下打印二叉树 III和 103. 二叉树的锯齿形层次遍历：先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行。

构造二叉树

相同点：输入都不是TreeNode，输出都是TreeNode

    1. 从前序与中序遍历序列构造二叉树和 剑指 Offer 07. 重建二叉树
    1. 从中序与后序遍历序列构造二叉树
    1. 根据前序和后序遍历构造二叉树

    3.jpg

    1. 将有序数组转换为二叉搜索树和 面试题 04.02. 最小高度树：将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。 注意此处的最小高度树还有个同名但不相关的题目 310. 最小高度树，别搞混了。

    1. 有序链表转换二叉搜索树：给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。 相反题： 114. 二叉树展开为链表：给定一个二叉树，原地将它展开为一个单链表。

      先序遍历的倒序

输出二叉树

    1. 输出二叉树：按一定规则逐层输出

    DFS+分治

  2. 剑指 Offer 37. 序列化二叉树和 297. 二叉树的序列化与反序列化：String和TreeNode的相互转换

二叉树的验证

注明：有多个类似题的是重点题目，其他的量力而行。

    1. 相同的树：检验是否相同。

  2. 剑指 Offer 28. 对称的二叉树和 101. 对称二叉树：判断一棵二叉树是不是对称的

  3. 剑指 Offer 55 - II. 平衡二叉树、 110. 平衡二叉树和 面试题 04.04. 检查平衡性：判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树

    1. 验证二叉搜索树和 面试题 04.05. 合法二叉搜索树：判断其是否是一个有效的二叉搜索树
    1. 验证二叉树：只有所有节点能够形成且只形成一颗有效的二叉树时，返回true；否则返回false。

    树就是无环的连通图！怎么检测是否存在环和计算连通分支数？当然是用并查集啦！

    1. 找到根节点
    2. 判断联通，成环
    1. 二叉树的完全性检验：确定它是否是一个完全二叉树。

    BFS

    1. 二叉树的堂兄弟节点：判断x和y是否为堂兄弟

    记录父节点

  8. 剑指 Offer 26. 树的子结构：判断B是不是A的子结构

    1. 另一个树的子树和 面试题 04.10. 检查子树：判断T2是否为T1的子树

二叉树的翻转

  1. 剑指 Offer 27. 二叉树的镜像和 226. 翻转二叉树：左右对称翻转
  2. 156.上下翻转二叉树：上下翻转

二叉树的深度和直径

  1. 剑指 Offer 55 - I. 二叉树的深度和 104. 二叉树的最大深度：找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
    1. 二叉树的最小深度：找出其最小深度。最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
    1. 二叉树的直径：计算直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。

二叉树的路径与路径和

    1. 二叉树的所有路径：给定一个二叉树，返回所有从根节点到叶子节点的路径。
    1. 路径总和：给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。
    1. 路径总和 II和 剑指 Offer 34. 二叉树中和为某一值的路径：给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。
    1. 路径总和 III和 面试题 04.12. 求和路径：打印节点数值总和等于某个给定值的所有路径的数量。注意，路径不一定非得从二叉树的根节点或叶节点开始或结束，但是其方向必须向下(只能从父节点指向子节点方向)。
    1. 树的遍历 + DFS $O(n^2)$
    2. HashMap 加速 $O(n)$
    1. 最长同值路径：给定一个二叉树，找到最长的路径，这个路径中的每个节点具有相同值。 这条路径可以经过也可以不经过根节点。
    1
2

    以node为起点的最长等值链长度
每次递归判断，左+1+右之和与最大值比较

二叉树的祖先

  1. 剑指 Offer 68 - I. 二叉搜索树的最近公共祖先和 235. 二叉搜索树的最近公共祖先：给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

    1
2
3
4
5
6
7

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if(root.val < p.val && root.val < q.val)
        return lowestCommonAncestor(root.right, p, q);
    if(root.val > p.val && root.val > q.val)
        return lowestCommonAncestor(root.left, p, q);
    return root;
}

  2. 剑指 Offer 68 - II. 二叉树的最近公共祖先和 236. 二叉树的最近公共祖先：给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

结束语

以上题目的整理仅个人之见，如果大家刷完这些题目还意犹未尽，建议在电脑上按关键词搜索，可以看到更多类似的题目。