深入理解二叉树和二叉搜索树

# 1. 介绍二叉树和二叉搜索树

## 1.1 二叉树的定义和性质

二叉树是一种常见的树状数据结构，其中每个节点最多有两个子节点。二叉树可以为空，或者由根节点和左右两个子树组成。二叉树的性质包括：

- 每个节点最多有两个子节点，分别称为左子节点和右子节点。
- 左子节点的值小于等于父节点的值，右子节点的值大于等于父节点的值。

## 1.2 二叉搜索树的定义和性质

二叉搜索树（Binary Search Tree，简称BST）是一种特殊的二叉树，它满足以下性质：

- 对于BST中的每个节点，其左子树的节点值都小于该节点的值，而其右子树的节点值都大于该节点的值。
- BST中不存在相同节点值的节点。
- BST的左右子树也是二叉搜索树。

二叉搜索树的这种性质使得它在查找、插入和删除节点等操作上具有高效性能。

下面我们将介绍二叉树的遍历算法。

# 2. 二叉树的遍历算法

二叉树的遍历是指按照一定的顺序访问二叉树的所有节点。常见的遍历方式包括前序遍历、中序遍历、后序遍历和层序遍历。下面将介绍这四种遍历算法及其实现。

### 2.1 前序遍历

前序遍历是指先访问根节点，然后按照先左后右的顺序遍历左子树和右子树。具体实现如下：

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
def preorderTraversal(root):
    if root is None:
        return []
    res = []
    stack = [root]
    while stack:
        node = stack.pop()
        res.append(node.val)
        if node.right is not None:
            stack.append(node.right)
        if node.left is not None:
            stack.append(node.left)
    return res

代码解释：

- 首先判断根节点是否为空，为空则直接返回空列表；
- 创建一个空列表res来保存遍历结果；
- 创建一个栈stack，将根节点入栈；
- 当栈中有节点时，从栈顶弹出一个节点，将其值添加到res列表中；
- 如果弹出节点的右子节点不为空，将其入栈；
- 如果弹出节点的左子节点不为空，将其入栈；
- 重复以上步骤，直到栈为空，完成遍历；
- 返回res列表作为遍历结果。

### 2.2 中序遍历

中序遍历是指先遍历左子树，然后访问根节点，最后遍历右子树。具体实现如下：

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    TreeNode curr = root;
    while (curr != null || !stack.isEmpty()) {
        while (curr != null) {
            stack.push(curr);
            curr = curr.left;
        }
        curr = stack.pop();
        res.add(curr.val);
        curr = curr.right;
    }
    return res;
}

代码解释：

- 首先创建一个空列表res来保存遍历结果；
- 创建一个栈stack和一个指针curr；
- 当curr不为空或者栈非空时，执行以下操作：
- 当curr不为空时，将curr入栈，并将curr更新为其左子节点；
- 当curr为空时，表示当前子树已经遍历完，将栈顶的节点弹出并添加到res列表中，并将curr更新为弹出节点的右子节点；
- 重复以上步骤，直到curr为空且栈为空，完成遍历；
- 返回res列表作为遍历结果。

### 2.3 后序遍历

后序遍历是指先遍历左子树，然后遍历右子树，最后访问根节点。具体实现如下：

function TreeNode(val) {
    this.val = val;
    this.left = this.right = null;
}

var postorderTraversal = function(root) {
    let res = [];
    let stack = [];
    let lastVisited = null;
    let curr = root;
    while (curr != null || stack.length > 0) {
        while (curr != null) {
            stack.push(curr);
            curr = curr.left;
        }
        let top = stack[stack.length - 1];
        if (top.right == null || top.right === lastVisited) {
            res.push(top.val);
            stack.pop();
            lastVisited = top;
        } else {
            curr = top.right;
        }
    }
    return res;
};

代码解释：

- 首先创建一个空数组res来保存遍历结果；
- 创建一个栈stack、一个记录上一个访问节点的变量lastVisited和一个指针curr；
- 当curr不为空或者栈非空时，执行以下操作：
- 当curr不为空时，将curr入栈，并将curr更新为其左子节点；
- 当curr为空时，表示当前子树的左子树已经遍历完，取出栈顶节点并判断其右子节点是否为空或者已被访问过：
- 如果右子节点为空或者已被访问过，则表示当前子树已经遍历完，将栈顶节点的值添加到res列表中，将栈顶元素出栈，并将lastVisited更新为栈顶元素；
- 如果右子节点不为空且未被访问过，则继续遍历右子树，将curr更新为右子节点；
- 重复以上步骤，直到curr为空且栈为空，完成遍历；
- 返回res数组作为遍历结果。

### 2.4 层序遍历

层序遍历是按照从上到下、从左到右的顺序逐层遍历二叉树的节点。使用队列来辅助遍历。具体实现如下：

class TreeNode:
    def __init__(self, v