树相关操作总结

1 树的结点定义

struct TreeNode{
    int val;
    TreeNode*left;
    TreeNode*right;
    TreeNode(int x):val(x),left(nullptr),right(nullptr){}
}

2 树的遍历

2.1 三种遍历方式

void traversal(TreeNode*root)
{
    if(root!=nullptr)
    {
        //visit(root)前序操作
        traversal(root->left);
        //visit(root)中序操作
        traversal(root->right);
        //visit(root)后序操作
    }
}

2.2 根据前+中序、后+中序构建二叉树

//前+中序
TreeNode*build(
    vector<int>&preorder,int preL,int preR,
    vector<int>&inorder,int inL,int inR,
    unordered_map<int,int>&pos
)
{
    if(preL>preR)return nullptr//递归返回条件
 
    //确定根结点    
    int rootVal=preorder[preL];
    TreeNode*root=new TreeNode(rootVal);
 
    int k=pos[rootVal];//这里k就是中序序列中根所在的位置的下标
    int leftSize=k-inL;
 
    //这里可借助草稿确定新的边界范围
    root->left=build(
        preorder,preL+1,preL+leftSize,
        inorder,inL,k-1,
        pos
    );
 
    root->right=build(
        preorder,preL+leftSize+1,preR,
        inorder,k+1,inR,
        pos
    );
 
    return root;
}

//后+中序
TreeNode*build(
    vector<int>&postorder,int postL,int postR,
    vector<int>&inorder,int inL,int inR,
    unordered_map<int,int>&pos
)
{
    if(postL>postR)return nullptr;//递归返回条件
 
    //确定根结点    
    int rootVal=postorder[postR];
    TreeNode*root=new TreeNode(rootVal);
 
    int k=pos[rootVal];//这里k就是中序序列中根所在的位置的下标
    int rightSize=inR-k;
 
    //这里可借助草稿确定新的边界范围
    root->left=build(
        postorder,postL,postR-rightSize-1,
        inorder,inL,k-1,
        pos
    );
 
    root->right=build(
        postorder,postR-rightSize,postR-1,
        inorder,k+1,inR,
        pos
    );
 
    return root;
}

而上述代码中涉及到哈希表pos的构建，因此整个二叉树的构建可以用下面的adapter函数来实现

TreeNode*buildTree(
    vector<int>&preorder,
    vector<int>&inorder
)
{
    unordered_map<int,int>pos;
    for(int i=0;i<inorder.size();i++)
    {       
        pos[inorder[i]]=i;
    }
    return build(
        preorder,0,preorder.size()-1,
        inorder,0,inorder.size()-1,
        pos
    );
}
 

2.3 计算树的高度

int height(TreeNode*root)
{
    if(root==nullptr)
    {
        return 0;
    }
    return max(height(root->left),height(root->right))+1;
}