二叉树 | 勿忘，须舍

介绍

树 是一种经常用到的数据结构，用来模拟具有树状结构性质的数据集合。

树里的每一个节点有一个根植和一个包含所有子节点的列表。从图的观点来看，树也可视为一个拥有N 个节点和N-1 条边的一个有向无环图。

二叉树是一种更为典型的树树状结构。如它名字所描述的那样，二叉树是每个节点最多有两个子树的树结构，通常子树被称作“左子树”和“右子树”。

满二叉树即每一层上的结点数都是最大结点数。若其深度为k，则有2^k-1个结点。

树的遍历

以二叉树为例，示例如下:

输入: [1,null,2,3]  
   1
    \
     2
    /
   3 

输出: [1,2,3]

前序遍历

前序遍历首先访问根节点，然后遍历左子树，最后遍历右子树。

python3 代码实现：

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        ret, stack = [], [root]
        while stack:
            node = stack.pop()
            if node:
                ret.append(node.val)
                #注意压入栈的顺序,先压入右孩子，再压入左孩子
                stack.append(node.right)
                stack.append(node.left)
        return ret

中序遍历

中序遍历是先遍历左子树，然后访问根节点，然后遍历右子树。

通常来说，对于二叉搜索树，我们可以通过中序遍历得到一个递增的有序序列。

后序遍历

后序遍历是先遍历左子树，然后遍历右子树，最后访问树的根节点。

值得注意的是，当你删除树中的节点时，删除过程将按照后序遍历的顺序进行。也就是说，当你删除一个节点时，你将首先删除它的左节点和它的右边的节点，然后再删除节点本身。

递归和迭代

递归或迭代方法实现算法。

递归(recursion)是程序调用自身的编程技巧。

迭代（iteration）是重复反馈过程的活动，其目的通常是为了逼近所需目标或结果。每一次对过程的重复称为一次“迭代”，而每一次迭代得到的结果会作为下一次迭代的初始值。