数据结构——树的理解

数据结构——树的理解

树

树是一种抽象数据类型（ADT）或是实现这种抽象数据类型的数据结构，用来模拟具有树状结构性质的数据集合。它是由 n(n>0)个有限节点组成一个具有层次关系的集合。

把它叫做「树」是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。

它具有以下的特点：

• 每个节点都只有有限个子节点或无子节点；
• 没有父节点的节点称为根节点；
• 每一个非根节点有且只有一个父节点；
• 除了根节点外，每个子节点可以分为多个不相交的子树；
• 树里面没有环路。

1. 树的遍历

• 先序遍历[根左右]
  1. 递归法
     1. 主要是看根的位置，如果根是在第一个位置的话，那么就是先进行append操作，在进行递归的操作。【不同遍历的方式只是append操作的位置不同而已，其他的核心的思想都是完全相同的】
  2. 颜色标记法
     1. 我们利用栈的思想【先进后出】，但是在入队列的时候我们对结点进行一个标记的处理，如果是第一次遇到我们标记为白色，否则的话我们将其标记为灰色。
  3. 迭代法
     1. 其实将递归转为迭代是比较常见的一种操作，通常都是通过栈或者队列的思想进行这个过程的转换的。
     2. 我们首先将root这个根节点放在stack这个栈中，只要我们的栈中的元素非空的话，我们就要一直进行循环的操作。
     3. 只要我们pop的结点非空的话[这是多余的，我们pop的结点一定是非空的！]，我们就将该值append到我们的最终的结果中，然后将其非空的子结点append到stack中，遵循的顺序是先右后左。
• 中序遍历[左根右]
  1. 递归法
  2. 颜色标记法
  3. 迭代法
     1. 相比于其他的两种方法，不同的顺序的遍历我们的迭代方法修改的地方还是比较多的，该代码的可塑性比较差。
     2. 还是使用stack栈的思想，对于中序遍历，我们首先是要将树的所有的左结点都增加到我们的stack中，然后我们将其进行pop操作，我们将pop出来的结点的val给append到我们的最终的结果中，但是此时我们需要注意的是，我们将我们的根节点移至pop的结点的右节点[这是个很关键的地方！]
     3. 循环至stack和我们的指针结点全部为空的时候，说明我们的遍历结束，返回结果。
• 后序遍历[左右根]
  1. 递归法
  2. 颜色标记法
  3. 迭代法
     1. 依旧是使用的stack的思想来完成这样的一个操作的。
     2. 这个是和前序遍历有着异曲同工之妙的，对于前序遍历的顺序是根左右，此时我们是左右根，所以我们是在前序的基础上稍作修改边可以得到我们的此时的后序遍历迭代代码。
     3. 但是需要注意的细节：在遍历的时候顺序是有区别的，stack是先进后出！！！
• 层序遍历[BFS]
  1. 使用队列的思想[先进先出] + 迭代
     1. 和之前的做法还是挺相似的，都是首先向队列中增加我们的初始结点；
     2. 因为我们是要按层遍历的，所以我们需要用一个循环将queue中的元素全部都pop到我们的最终结果中，代表的是我们将该层的结点全部都遍历完了，但是我们需要注意的是，我们在弹出该结点的元素之后，我们紧接着要对这个元素的左右结点进行判断，如存在就进行append的操作，这是下一层的结点。
     3. 注意：我们可以对这个问题进行进一步的讨论，其实就是在这个的基础上进一步将每层都用一个数组进行区分。也只是在我们之前的代码上做一下调整，在我们每次进入stack循环主体的时候都创建一个新的列表，然后在循环的最后将装有每层元素的列表append到我们最后的结果中即可。
  2. 递归法[使用深度优先搜索DFS]—针对我们每层的元素都单独保存的情况
     1. 首先要对最终结果中的列表的数量和当前的层数进行比较，如果层数较大的话，则表明我们是需要增加新的列表，以保存当前层的结点。
     2. 是否能使用递归这种思路完成BFS这样的搜索？

1. 给出遍历的结果，恢复树的结构

• 前序 + 中序 à 二叉树
  1. 递归
     1. 递归这样的思路还是比较好想到的，解决这样的问题最为关键的就是画图，通过在纸上的写写画画很容易能够想到解决方案的。
     2. 对于给出的前序和中序遍历的结果，我们可以找到每个树的根节点[前序遍历的第一个结点就是这棵树的root]，依据这个根节点我们在中序遍历中找到该索引值，那么我们可以将在该索引值的左边的元素就当成是我们还原的树的左子树，相似的，该索引值的右边的元素就是树的右子树。
     3. 故而，我们在找到根节点之后，将两个列表可以分成是四个部分，分别都是对应树的左子树和右子树，我们要做的就是找到这些个子树的分割点[这也是这个问题的一个难点，可以通过画图得到]。
• 后序 + 中序 à 二叉树
  1. 递归
     1. 这个的思路和之前的基本上是一致的，都是通过找到根节点的位置，从而可以确定树的左子树和右子树的元素情况，我们继续找到不同子树的索引的范围，进行递归就可以完成我们树的创建。
     2.  

1. 树的深度问题

• 树的最大深度
  1. 递归
     1. 递归终止的条件:   if not root:     return 0
     2. 我们每次循环都意味着我们的层数是增加1的，返回左右子树中最大的深度，作为我们的最终的结果输出。
  2. 迭代
     1. 这个问题可以看成是层次遍历中的子问题，只是我们无需将元素增加到列表中，我们只要是返回列表的长度即可。
     2. 所以我们直接将原来的加入空列表的操作，改成是index += 1这样的操作，最后返回我们的index即可。但是注意的是：仍然是使用的队列！！！
• 树的最小深度
  1. 递归
     1. 这里和求解树的最大深度不太一样的，但是整体的思路还是类似的。
     2. 在这里有一个最为主要的和最大深度不一样的地方就是，如果我们的一个子树是空的的话，我们返回的只能是另一个存在的子树的深度，而不是判断出来的最小的值。
  2. 迭代
     1. 同样的使用stack这样的一个栈的思想；
     2. 我们在进行入栈的操作的时候我们就给出当前的深度，我们保存每次的最小的深度，在这个解法中我们不需要单独的考虑子树是否存在的问题，因为不存在子树的话，我们这个结点就不会执行入栈的操作[此时可以使用栈，当然也是可以使用index索引的操作的，也就是直接在最大深度的基础上进行修改的！]
• 平衡树的问题
  1. 递归
     1. 我们可以使用一个辅助函数来检查每个子树的最大深度，以此来判断两边的子树的高度是否是符合要求的。[这是自上而下的判断的方式，是先求出长度在看是否是满足条件的]
     2. 同样的，我们可以采用自底向上的递归的方式[先判断是否是平衡树在进行递归]。我们需要使用辅助函数，
        1. 辅助函数的主要的作用就是判断子树的左右深度是否超过了2.

1. 1. 1. 1.     def Helper(self,root):
         2.            if not root:
         3.                   return 0
         4.            left = self.Helper(root.left)
         5.            if left == -1:
         6.                   return -1
         7.            right = self.Helper(root.right)
         8.            if right == -1:
         9.                   return -1
         10.            if abs(left - right) < 2:
         11.                   return max(left, right) + 1
         12.            else:
         13.                   return -1

1. 二叉树的恢复问题

• 二叉搜索树中的两个结点被错误的交换à正确的二叉树
  1. 鉴于二叉搜索树的一个最大的特点，用中序遍历的方式得到的结果是从小到大的顺序排列的。所以我们可以将原来的问题进行拆分称为三个部分：1.对错误的子树进行中序遍历；2.对遍历结果进行遍历找到被交换了的数字；3.在树中交换这两个错误的结点。其中比较不好理解的就是如何找到这两个交换了的数字。但是我们可以这么来理解，在正常的递增的序列中，nums[i] < nums[i+1]是成立的，所以只要不符合这个条件的i出现了，我们就需要将这个数nums[i]记下来，说明找到一个了，之后在进行遍历直至找到第二个元素。然后我们将这样的两个值返回。
  2. 我们可以再上述方式的基础上进一步的简化我们的操作。因为对于我们的二叉搜索树中序遍历的时候，我们的根节点是左子树的结点的值是肯定小于该根节点的值的，我们可以再遍历子树的时候就直接找到这样的两个结点，并且将这两个结点的信息存储在我们的指针结点中，在最后我们交换指针结点的值即可。[其实是对前面提到的三个步骤的优化处理，将第一二步骤结合起来了！]

1. 二叉搜索树

• 不同的二叉搜索树
  1. 对于二叉搜索树而言，他的构造的方式还是比较好理解的。现在我们要做的就是给出不同的根节点，都可以构造出我们的搜索树。
  2. 我们可以使用递归的方式来构建树。我们的helper函数传入的参数为(start,end)这样的两个参数。我们递归终止的条件就是start > end。否则的话小于start的部分就是左子树，而大于start的部分就是右子树部分。
  3. 最后在构建树的时候，我们使用一个双层的循环。为当前的结点找到他的左右子节点。
• 验证二叉搜索树
  1. 利用定义来证明
     1. 对于二叉搜索树使用中序遍历的时候他是递增的结果，所以我们将需要验证的二叉搜索树进行中序遍历，然后我们比较结果中的元素是否是递增的，是返回为True 否则为False。
  2. 递归法
     1. 对于二叉搜索树中的每个结点都是存在上下界的[除去root结点]，所以我们判断每个结点的值是否是超过了界限从而可以判断我们的二叉搜索树是否为真。
• 判断是否是对称二叉树
  1. 迭代
     1. 我们使用stack的思想，同时将树的下一层按顺序入栈，然后我们比较pop后的值是否是相等的，不等的话直接return false；否则继续进行入栈出栈的操作
  2. 递归
     1. 递归终止的条件就是返回true和false的情况，但是我们需要同时对树的(left.left, right.right) && (left.right, right.left)都需要满足！

1. 路径问题

• 如何表示出二叉树的路径
  1. DFS + 回溯算法
     1. 我们通过深度优先搜索将每个支路的结点都进行遍历，递归终止的条件是我们遍历的结点已经没有子结点的时候，便可以将路径返回，但是注意此时需要的是深拷贝。
     2. 回溯中一个关键的地方就是撤销的操作，在对于树的撤回操作是针对我们左右子树都走完的情况下在撤回的！