二叉树算法（回溯，动态规划，迭代）

序言

二叉树题型的算法主要分为回溯，动态规划，迭代三类。从本质上三者都是在遍历算法基础上的修改。回溯关心的是在每个结点的访问过程中如何更新结果；动态规划关心的是如何拆解出子问题，不具体分析每个结点的状态，而是通过划分子问题让其通过基本问题递归解决；迭代主要是指BFS层序遍历，适用于与深度（或高度）相关的问题求解

二叉树基本结构

  1. 二叉树
1
2
3
4
5
6
7
class TreeNode {
public:
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
  1. 多叉树
1
2
3
4
5
class TreeNode {
public:
    int val;
    vector<TreeNode *> children;
};

二叉树遍历

  1. 递归遍历

前序位置：刚进入当前子树根结点的时候（已知根结点信息）

中序位置：访问完左子树后，准备访问右子树的时候（已知根，左孩子结点信息）

后序位置：访问完左右子树后的，回溯到当前子树根结点的时候（已知根，左孩子，右孩子结点信息）

1
2
3
4
5
6
7
8
9
void traverse(TreeNode* root)
{
    if (root==NULL)return;
    // 前序位置
    traverse(root->left);
    // 中序位置
    traverse(root->right);
    // 后序位置
}
  1. 层序遍历

通过对每层访问后完后栈内元素个数的统计可以实现层数的更新

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void traverse(TreeNode* root)
{
    if(root==NULL)return;
    queue<TreeNode*> q;
    q.push(root);
    
    int depth = 0;
    while(!q.empty())
    {
        size_t sz = q.size();
        for (size_t i=0;i<sz;i++)
        {
            TreeNode *cur = q.front();
            q.pop();
            if (cur->left!=NULL)
                q.push(cur->left);
            if (cur->right!=NULL)
                q.push(cur->right);
        }
        depth++;
    }
}

二叉树题型解法

回溯（DFS）

基本思想

回溯关心的是在每个结点的访问过程中如何更新结果，着眼点在结点间移动的过程

在求解过程中假定当前处理的为其中一颗子树，考虑两个问题：

  1. 前/中序位置：进入当前层后要做的事
  2. 后序位置：回溯到父结点前要做的事

举例

二叉树的最大深度

在结点访问时更新depth，如果为根结点则表示为可能的当前子树深度最大值，更新全局最大深度（进入时）。当返回到父结点前，表示当前子树已经遍历完成，父结点的depth应为当前depth-1（回溯前）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int max_depth = 0;
int depth = 0;
void traverse(TreeNode* root)
{
    if (root==NULL)return;
    depth++;
    if (root->left==NULL && root->right==NULL)
        max_depth=max(max_depth,depth);
    traverse(root->left);
    traverse(root->right);
    depth--;
}


int maxDepth(TreeNode* root)
{
    if(root==NULL)return 0;
    traverse(root);
    return max_depth;
}

动态规划（分解子问题）

基本思想

动态规划关心的是如何拆解出子问题，不具体分析每个结点的状态，而是通过划分子问题让其通过基本问题递归解决，着眼点在结构相同的子问题

在求解过程中需要考虑三个问题

  1. 确定问题：给当前的计算过程一种解释
  2. 解决基准问题：思考当输入值为基础值时，其返回的结果是什么。该步用于确定递归终止条件
  3. 拆解问题：考虑在当前的普通输入时，应该如何解决问题

举例

二叉树的最大深度
  1. 确定问题：计算以root为根结点的二叉树的最大深度并返回最大深度
  2. 解决基准问题：当root为空指针时，表示该树空，返回0
  3. 拆解问题：当前结点的最大深度即为左右子树中的最大深度+1，所以只需要获取左右子树的最大深度后+1即可
1
2
3
4
5
6
7
int maxDepth(TreeNode* root)
{
    if(root==NULL)return 0;
    int left_max_depth = maxDepth(root->left);
    int right_max_depth = maxDepth(root->right);
    return max(left_max_depth,right_max_depth)+1;
}

迭代（BFS）

同上二叉树层序遍历

其他

建立二叉树

可以看作动态规划的思想

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 递归构造二叉树，处理空节点
TreeNode* build_tree(const vector<int>& arr, int index) {
    // 越界或遇到空节点值
    if (index >= arr.size() || arr[index] == -1) {
        return nullptr;
    }

    // 创建当前节点
    TreeNode* node = new TreeNode(arr[index]);

    // 递归构造左、右子树
    node->left = build_tree(arr, 2 * index + 1);
    node->right = build_tree(arr, 2 * index + 2);

    return node;
}