二叉树遍历 | 二叉树查找 | 二叉树重建
二叉树基础
二叉树是一种典型的树树状结构。如它名字所描述的那样,二叉树是每个节点最多有两个子树的树结构,通常子树被称作“左子树”和“右子树”。
完全二叉树的一些公式:
- 第 n 层的节点数最多为 2(n 次方)个节点
- n 层二叉树最多有 2(0 次方)+…+2(n 次方)=2(n+1 次方)-1 个节点
- 第一个非叶子节点:length/2
- 一个节点的孩子节点:2n、2n+1
基本构造
1 | // 节点的构造函数 |
各个细分问题
非递归地实现遍历
非递归地实现中序遍历
1 | function middle_orderTraversal(root) { |
非递归地实现先序遍历
1 | function pre_orderTraversal(root) { |
非递归地实现后序遍历
1 | function last_orderTraversal(root) { |
二叉树重建,对称,镜像
二叉树重建
二叉树的重建:
输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树
假设输入的前序遍历和中序遍历的结果中都不含重复的数字
思路:
前序遍历找到根节点 root,
找到 root 在中序遍历中的位置 =》进而获得左子树和右子树的长度
根据获得的长度,截取左子树的中序遍历,右子树的中序遍历
根据获得的长度,截取左子树的前序遍历,右子树的前序遍历
根据子树的中序,前序遍历,递归重建二叉树
1 | // pre,mid 是前序,中序遍历的结果数组 |
二叉树对称
判断一棵二叉树是不是对称的:
如果一颗二叉树同次二叉树的镜像是同样的,定义为对称的
镜像二叉树:两棵二叉树根节点相同,但左右两个子节点交换了位置
思路:
两个根节点相等
左子树的右节点和右子树的左节点相同
右子树的左节点和左子树的右节点相同
1 | // 传入树的根节点 |
二叉树镜像处理
操作给定的二叉树,将其变化为源二叉树的镜像
思路:递归交换所有节点左右节点的位置
1 | function Mirror(root) { |
平衡二叉树
输入一颗二叉树,判断该二叉树是否是平衡二叉树
平衡二叉树:每个子树的深度之差不超过 1
1 | function IsBalanced_Solution(Root) { |
序列化与反序列化
实现两个函数,序列化和反序列化二叉树
思路:
若一颗二叉树是不完全的,我们至少需要两个遍历才能将它重建(像题目重建二叉树一样)
但是这种方式仍然有一定的局限性,比如二叉树中不能出现重复节点。
如果二叉树是一颗完全二叉树,我们只需要知道前序遍历即可将它重建。
因此在序列化时二叉树时,可以将空节点使用特殊符号存储起来,这样就可以模拟一棵完全二叉树的前序遍历
在重建二叉树时,当遇到特殊符号当空节点进行处理
1 | // 序列化,传入根节点 |
查找二叉树
找到二叉树中第 k 小的节点
思路:中序遍历后,即是按大小排序,然后取第 k 个即可
1 | // 递归的实现 |
后序反判断
输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出 Yes,否则输出 No。假设输入的数组的任意两个数字都互不相同
1 | function Verify_Squence_OfBST(sequence) { |
二叉树最小深度
给定一个二叉树,找出其最小深度
思路:如果左子树为空,则返回右子树最小深度+1,如果右子树为空,则返回左子树最小深度+1,
如果都非空,则返回两边最小值+1,最后一步取最小值,确保得到最小路径
1 | function minDepth(node) { |
二叉树查找求和
输入一颗二叉树的跟节点和一个整数,打印出二叉树中结点值的和为输入整数的所有路径
路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径
思路:
设定一个结果数组 result 来存储所有符合条件的路径,设定一个栈 stack 来存储当前路径中的节点,设定一个和 sum 来标识当前路径之和
从根结点开始深度优先遍历,每经过一个节点,将节点入栈,到达叶子节点,且当前路径之和等于给定目标值,则找到一个可行的解决方案,将其加入结果数组
遍历到二叉树的某个节点时有 2 个可能的选项,选择前往左子树或右子树
若存在左子树,继续向左子树递归,若存在右子树,继续向右子树递归
若上述条件均不满足,或已经遍历过,将当前节点出栈,向上回溯
1 | function FindPath(Root, expectNumber) { |
查找下一个节点
给定一个二叉树和其中的一个结点,请找出中序遍历顺序的下一个结点并且返回
注意,树中的结点不仅包含左右子结点,同时包含指向父结点的指针
思路:
中序遍历:左-根-右
所以寻找下一个节点的优先级反过来, 右-根-左
右节点不为空-取右节点的最左侧节点
右节点为空-如果节点是父亲节点的左节点,取父节点
右节点为空-如果节点是父节点的右节点 父节点已经被遍历过了,再往上层寻找
左节点一定在当前节点之前被遍历过了
1 | function GetNext(pNode) { |
判断子树结构
输入两颗二叉树 A,B,判断 B 是不是 A 的子结构
思路:
首先找到 A 树中和 B 树相同的节点
从此节点开始,递归 AB 树比较是否有不同的节点
1 | function HasSubtree(RootA, RootB) { |
结语
以上是二叉树的相关算法问题,难度较大,希望能有助于自已多看
如果对您有帮助,建议打个钱哦亲~~