C++算法集锦：二叉树的基本操作

• 二叉树的最小深度
• 从下到上打印二叉树
• 从中序与后序遍历序列构造二叉树
• 从前序与中序遍历序列构造二叉树

牛客链接：NC234 二叉树的最小深度

题解1：深度优先遍历

沿着深度进行遍历，到根节点判断当前深度是否小于最长深度，是则替换。

class Solution {
public:
    
    void lowerdeep(TreeNode* root,int layer, int &ans){
        if(root->left ==nullptr && root->right ==nullptr){
            ans = min(layer,ans);
            return;
        }
        if(layer > ans)              //剪枝
            return;
            
        if(root->left)
            lowerdeep(root->left,layer+1, ans);  //递归寻找左右子树深度
        if(root->right)
            lowerdeep(root->right,layer+1, ans);
        
    }
    int run(TreeNode* root) {
        // write code here
        if(root ==nullptr)
            return 0;
        int ans = INT_MAX;
        lowerdeep(root,1,ans);
        return ans;
    }
};

解法2：广度优先遍历

从跟节点到叶子结点的广度搜索得到的第一个叶子结点的深度就是答案。

class Solution {
public:
    
    int run(TreeNode* root) {
        // write code here
        if(!root)
            return 0;
        vector dq = {root};
        vector temp;
        int layer = 0;
        while(dq.size()>0){
            ++layer;
            temp.clear();
            for(TreeNode* node : dq)
            {
                if(!node->left && !node->right)   //广度搜索到的第一个叶子结点的深度就是答案。
                    return layer;
                if(node->left)
                    temp.emplace_back(node->left);
                if(node->right)
                    temp.emplace_back(node->right);
            }
            dq.clear();
            dq = temp;
        }
        return 0;
    }
};

牛客链接：NC224 从下到上打印二叉树

题解1：深度优先遍历

定义一个表示层的对象，在深度遍历的时候，将每一层的结点加入到最终的结果集中对应层中。

class Solution {
public:
    
    void printnode(TreeNode* root,vector > &ans, int layer){
        if(root==nullptr)
            return;
        if(ans.size()<=layer){
            ans.push_back(vector());
        }
        ans[layer].push_back(root->val);
        
        printnode(root->left,ans,layer+1);
        printnode(root->right,ans,layer+1);
    }

    vector > levelOrderBottom(TreeNode* root) {
        // write code here
        vector > ans;
        printnode(root,ans,0);
        reverse(ans.begin(), ans.end()); //ans本身是保存第一层到最后一层，题目要求为最后一层到第一层。
        return ans;
    }
};

题解1：广度优先遍历

从第一层开始，每次将一层的所有结果保存，同时将当前层的所有子节点都保存在另外一个vector中，用于下次一定循环遍历。

class Solution {
public:
    
    vector > levelOrderBottom(TreeNode* root) {
        // write code here
        vector > ans;
        vector dq = {root};
        vector temp_dq;
        vector temp_ans;
        while(dq.size()>0){
            temp_dq.clear();
            temp_ans.clear();
            for(TreeNode* node: dq)
            {
                temp_ans.emplace_back(node->val);
                if(node->left!=nullptr)
                    temp_dq.emplace_back(node->left);
                if(node->right!=nullptr)
                    temp_dq.emplace_back(node->right);
            }
            dq.clear();
            ans.emplace_back(temp_ans);
            dq=temp_dq;
        }
                
        reverse(ans.begin(), ans.end());
        return ans;
    }
};

牛客链接：NC223 从中序与后序遍历序列构造二叉树

解题思路：

采用DFS算法构建树，找到后序排序中的结尾值，该值为当前树的根节点。根据根节点在中序遍历中的位置将中序遍历分为左子树和右子树的中序遍历数组，依次构建左子树与右子树。

class Solution {
public:
    
    TreeNode* build(vector& inorder, vector& postorder,int in_start, int in_end, int pos_start, int pos_end){
        if(in_start>in_end) return 0;
        TreeNode* node = new TreeNode(postorder[pos_end]);   //后序遍历最后一个为根节点
        //计算左子树的长度，相应的也就得出了右子树的长度。
        int position = distance(inorder.begin(),find(inorder.begin(), inorder.end(), postorder[pos_end]));
        node->left = build(inorder, postorder, in_start, position-1, pos_start, pos_start+position-1-in_start);
        node->right = build(inorder, postorder, position+1, in_end, pos_start+position-in_start, pos_end-1);
        
        return node;
    }
    
    TreeNode* buildTree(vector& inorder, vector& postorder) {
        // write code here
        TreeNode* node = build(inorder, postorder, 0, inorder.size()-1,  0,  postorder.size()-1);
        return node;
    }
};

leetcode链接：105. 从前序与中序遍历序列构造二叉树

思想同从中序与后序遍历序列构造二叉树

class Solution {
public:
    TreeNode* buildTree(vector& preorder, vector& inorder) {
        TreeNode* head = build(inorder, preorder, 0, inorder.size()-1,  0,  preorder.size()-1);
        return head;
    }
    TreeNode* build(vector& inorder, vector& preorder,int in_start, int in_end, int pre_start, int pre_end)
    {
        if(in_start>in_end) return nullptr;
        TreeNode *node = new TreeNode(preorder[pre_start]);
        //找到当前头结点的位置。
        int position = distance(inorder.begin(),find(inorder.begin(),inorder.end(),preorder[pre_start]));
        //建立左子树
        node->left = build(inorder, preorder, in_start, position-1, pre_start+1, pre_start + position - in_start);
        //建立右子树
        node->right = build(inorder, preorder, position+1, in_end, pre_start+position - in_start +1, pre_end);
        return node;
    }
};