二叉树算法（回溯，动态规划，迭代）
目录
序言
二叉树题型的算法主要分为回溯，动态规划，迭代三类。从本质上三者都是在遍历算法基础上的修改。回溯关心的是在每个结点的访问过程中如何更新结果；动态规划关心的是如何拆解出子问题，不具体分析每个结点的状态，而是通过划分子问题让其通过基本问题递归解决；迭代主要是指BFS层序遍历，适用于与深度（或高度）相关的问题求解
二叉树基本结构
- 二叉树
class TreeNode {
public:
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};- 多叉树
class TreeNode {
public:
int val;
vector<TreeNode *> children;
};二叉树遍历
- 递归遍历
前序位置：刚进入当前子树根结点的时候（已知根结点信息）
中序位置：访问完左子树后，准备访问右子树的时候（已知根，左孩子结点信息）
后序位置：访问完左右子树后的，回溯到当前子树根结点的时候（已知根，左孩子，右孩子结点信息）
void traverse(TreeNode* root)
{
if (root==NULL)return;
// 前序位置
traverse(root->left);
// 中序位置
traverse(root->right);
// 后序位置
}- 层序遍历
通过对每层访问后完后栈内元素个数的统计可以实现层数的更新
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）
基本思想
回溯关心的是在每个结点的访问过程中如何更新结果，着眼点在结点间移动的过程
在求解过程中假定当前处理的为其中一颗子树，考虑两个问题：
- 前/中序位置：进入当前层后要做的事
- 后序位置：回溯到父结点前要做的事
举例
二叉树的最大深度
在结点访问时更新depth，如果为根结点则表示为可能的当前子树深度最大值，更新全局最大深度（进入时）。当返回到父结点前，表示当前子树已经遍历完成，父结点的depth应为当前depth-1（回溯前）
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;
}动态规划（分解子问题）
基本思想
动态规划关心的是如何拆解出子问题，不具体分析每个结点的状态，而是通过划分子问题让其通过基本问题递归解决，着眼点在结构相同的子问题
在求解过程中需要考虑三个问题
- 确定问题：给当前的计算过程一种解释
- 解决基准问题：思考当输入值为基础值时，其返回的结果是什么。该步用于确定递归终止条件
- 拆解问题：考虑在当前的普通输入时，应该如何解决问题
举例
二叉树的最大深度
- 确定问题：计算以root为根结点的二叉树的最大深度并返回最大深度
- 解决基准问题：当root为空指针时，表示该树空，返回0
- 拆解问题：当前结点的最大深度即为左右子树中的最大深度+1，所以只需要获取左右子树的最大深度后+1即可
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）
同上二叉树层序遍历
建立二叉树
已知完全二叉树数组
可以看作动态规划的思想
// 递归构造二叉树，处理空节点
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;
}已知前序序列和中序序列
主要任务是分隔出左右子树的区间
// 构造以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;
}已知前序序列构建二叉搜索树
主要任务是分隔出左右子树的区间
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;
}