子非鱼的技术博客
0%

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

Posted on
Symbols count in article: 4.3k Reading time ≈ 11 mins.

序言

二叉树题型的算法主要分为回溯，动态规划，迭代三类。从本质上三者都是在遍历算法基础上的修改。回溯关心的是在每个结点的访问过程中如何更新结果；动态规划关心的是如何拆解出子问题，不具体分析每个结点的状态，而是通过划分子问题让其通过基本问题递归解决；迭代主要是指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;
}

已知前序序列和中序序列

主要任务是分隔出左右子树的区间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
// 构造以root为根结点的二叉树，返回root
TreeNode* build_tree(vector<int>& preorder, vector<int>& inorder,
                     int p_start, int p_end, int i_start, int i_end) {
    if (p_start < 0 || p_end >= preorder.size() || i_start < 0 ||
        i_end >= inorder.size() || p_start > p_end || i_start > i_end)
        return nullptr;
    TreeNode* root = new TreeNode(preorder[p_start]);
    int root_val_idx_in_inorder = -1;
    for (int j = i_start; j <= i_end; j++) {
        if (inorder[j] == preorder[p_start]) {
            root_val_idx_in_inorder = j;
            break;
        }
    }

    int left_node_count = max(0,root_val_idx_in_inorder - i_start);
    int node_count = i_end - i_start + 1; // include root
    int right_node_count = node_count - left_node_count - 1;

    root->left =
        build_tree(preorder, inorder, p_start+1, p_start+left_node_count,
                   i_start, root_val_idx_in_inorder - 1);
    root->right =
        build_tree(preorder, inorder, p_start + left_node_count + 1, p_end,
                   root_val_idx_in_inorder+1, i_end);
    return root;
}

TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    TreeNode *root;
    root = build_tree(preorder, inorder,0,preorder.size()-1,0,inorder.size()-1);
    return root;
}

已知前序序列构建二叉搜索树

主要任务是分隔出左右子树的区间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
TreeNode *build_tree(vector<int>& preorder,int p_start,int p_end)
{
    if (p_start<0||p_end>=preorder.size()||p_start>p_end)
        return nullptr;

    TreeNode *root = new TreeNode(preorder[p_start]);
    int right_tree_start_idx = p_end+1;
    for (int i=p_start;i<=p_end;i++)
    {
        if (preorder[i] > preorder[p_start])
        {
            right_tree_start_idx = i;
            break;
        }
    }

    root->left = build_tree(preorder,p_start+1,right_tree_start_idx-1);
    root->right = build_tree(preorder,right_tree_start_idx,p_end);

    return root;
}

TreeNode* bstFromPreorder(vector<int>& preorder) {
    TreeNode *root;
    root = build_tree(preorder, 0,preorder.size()-1);
    return root;
}