「算法总结」 20 道题轻松搞定 BAT 面试——二叉树 几个概念 完全二叉树：若二叉树的高度是h，除第h层之外，其他（1h-1）层的节点数都达到了最大个数，并且第h层的节点都连续的集中在最左边。想到点什么没？实际上，完全二叉树和堆联系比较紧密哈~~ 满二叉树：除最后一层外，每一层上的所有节点都有两个子节点，最后一层都是叶子节点。 哈夫曼树：给定n个权值作为n的叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman tree)。 二叉排序树：又称二叉查找树（Binary Search Tree），亦称二叉搜索树。二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：若左子树不空，则左子树上所有结点的值均小于它的根结点的值；若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；左、右子树也分别为二叉排序树；没有键值相等的节点 二分查找的时间复杂度是O(log(n))，最坏情况下的时间复杂度是O(n)（相当于顺序查找） 平衡二叉树：又称 AVL 树。平衡二叉树是二叉搜索树的进化版，所谓平衡二叉树指的是，左右两个子树的高度差的绝对值不超过 1。 红黑树：红黑树是每个节点都带颜色的树，节点颜色或是红色或是黑色，红黑树是一种查找树。红黑树有一个重要的性质，从根节点到叶子节点的最长的路径不多于最短的路径的长度的两倍。对于红黑树，插入，删除，查找的复杂度都是O（log N）。 1. 求二叉树中的节点个数 递归解法： （1）如果二叉树为空，节点个数为0 （2）如果不为空，二叉树节点个数 = 左子树节点个数 + 右子树节点个数 + 1 参考代码如下： 2. 求二叉树的最大层数(最大深度) 剑指offer：[二叉树的深度] 递归解法： （1）如果二叉树为空，二叉树的深度为0 （2）如果二叉树不为空，二叉树的深度 = max(左子树深度， 右子树深度) + 1 参考代码如下： 2.1 二叉树的最小深度 LeetCode： 给定一个二叉树，找出其最小深度。 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。 
<figcaption></figcaption> 3. 先序遍历/前序遍历 LeetCode：[Binary Tree Preorder Traversal]给定二叉树，返回其节点值的前序遍历。 
递归 非递归 方法一： 方法二： 4. 中序遍历 LeetCode：[Binary Tree Inorder Traversal]给定二叉树，返回其节点值的中序遍历。 
递归 非递归 5. 后序遍历 Leetcode：[Binary Tree Postorder Traversal]给定二叉树，返回其节点值的后序遍历。 
递归 非递归 方法一： 方法二： 方法三(推荐)： 6. 分层遍历 LeetCode：Binary Tree Level Order Traversal剑指offer：从上往下打印二叉树 剑指offer：把二叉树打印成多行给定二叉树，返回其节点值的级别顺序遍历。 
6.1 自下而上分层遍历 LeetCode：[Binary Tree Level Order Traversal II]给定二叉树，返回其节点值的自下而上级别顺序遍历。 6.2 按之字形顺序打印二叉树 剑指offer：[按之字形顺序打印二叉树]请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。 设两个栈，s2存放奇数层，s1存放偶数层 遍历s2节点的同时按照左子树、右子树的顺序加入s1， 遍历s1节点的同时按照右子树、左子树的顺序加入s2 7. 求二叉树第K层的节点个数 8. 求二叉树第K层的叶子节点个数 9. 判断两棵二叉树是否结构相同 LeetCode：[Same Tree] 给定两个二叉树，编写一个函数来检查它们是否相同。 递归解法： （1）如果两棵二叉树都为空，返回真 （2）如果两棵二叉树一棵为空，另一棵不为空，返回假 （3）如果两棵二叉树都不为空，如果对应的左子树和右子树都同构返回真，其他返回假 10. 判断二叉树是不是平衡二叉树 LeetCode：[Balanced Binary Tree] 给定二叉树，确定它是否是高度平衡的。 对于此问题，高度平衡二叉树定义为： 一个二叉树，其中每个节点的两个子树的深度差不相差超过1。 递归解法： （1）如果二叉树为空，返回真 （2）如果二叉树不为空，如果左子树和右子树高度相差不大于1且左子树和右子树都是AVL树，返回真，其他返回假 11. 求二叉树的镜像 剑指offer：[二叉树的镜像]LeetCode：[Invert Binary Tree]反转二叉树 
11.1 对称二叉树 剑指offer：[对称的二叉树] LeetCode：[Symmetric Tree]给定一个二叉树，检查它是否是镜像对称的。 
12. 求二叉树中两个节点的最低公共祖先节点 LeetCode：[Lowest Common Ancestor of a Binary Tree] 给定二叉树，找到树中两个给定节点的最低共同祖先（LCA）。 
递归解法： （1）如果两个节点分别在根节点的左子树和右子树，则返回根节点 （2）如果两个节点都在左子树，则递归处理左子树；如果两个节点都在右子树，则递归处理右子树 12.1 求二叉搜索树的最近公共祖先 LeetCode：[Lowest Common Ancestor of a Binary Search Tree] 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。” 
注意二叉搜索树的特性： < < 13. 求二叉树的直径 LeetCode：[Diameter of Binary Tree]给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过根结点。 
递归解法：对于每个节点，它的最长路径等于左子树的最长路径+右子树的最长路径 14. 由前序遍历序列和中序遍历序列重建二叉树 剑指offer：[重建二叉树]根据一棵树的前序遍历与中序遍历构造二叉树。 
14.1 从中序与后序遍历序列构造二叉树 LeetCode：[Construct Binary Tree from Inorder and Postorder Traversal]根据一棵树的中序遍历与后序遍历构造二叉树。 
本题与“从前序与中序遍历序列构造二叉树”是一个套路。唯一的区别是，后序序列的最后一个节点是根节点，因此我们要从后序序列的最后一个节点入手，再去中序序列中找到这个节点。在这个节点左侧的属于根节点的左子树部分，右侧的属于根节点右子树部分。然后根据左右子树节点的数量，在后序序列中找到他们各自的后序序列。比左子树节点个数为5，那么在后序序列中前五个节点就是左子树节点，之后的节点除了最后一个节点都是右子树节点。 提示：根据前序和后序遍历无法构造出唯一的二叉树 15. 判断二叉树是不是完全二叉树 完全二叉树是指最后一层左边是满的，右边可能慢也不能不满，然后其余层都是满的，根据这个特性，利用层遍历。如果我们当前遍历到了NULL结点，如果后续还有非NULL结点，说明是非完全二叉树。 16. 树的子结构 剑指offer：[树的子结构]输入两棵二叉树A，B，判断B是不是A的子结构。 17. 二叉树中和为某一值的路径 剑指offer：[二叉树中和为某一值的路径]输入一颗二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。 18. 二叉树的下一个结点 剑指offer：[二叉树的下一个结点]给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。 19. 序列化二叉树 剑指offer：[序列化二叉树] LeetCode：[Serialize and Deserialize Binary Tree]请实现两个函数，分别用来序列化和反序列化二叉树 
20. 二叉搜索树的第k个结点 剑指offer：[二叉搜索树的第k个结点]给定一棵二叉搜索树，请找出其中的第k小的结点。例如， （5，3，7，2，4，6，8）中，按结点数值大小顺序第三小结点的值为4。 
因为二叉搜索树按照中序遍历的顺序打印出来就是排好序的，所以，我们按照中序遍历找到第k个结点就是题目所求的结点。
2024最新激活全家桶教程，稳定运行到2099年，请移步至置顶文章：https://sigusoft.com/99576.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处：https://sigusoft.com/84858.html
