二叉树的最小深度

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

题解1：深度优先遍历

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

/** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * }; */
class Solution {
   
public:
    /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param root TreeNode类 * @return int整型 */
    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：广度优先遍历

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

/** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * }; */
class Solution {
   
public:
    /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param root TreeNode类 * @return int整型 */
    int run(TreeNode* root) {
   
        // write code here
        if(!root)
            return 0;
        vector<TreeNode*> dq = {
   root};
        vector<TreeNode*> 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：深度优先遍历

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

/** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * }; */
class Solution {
   
public:
    /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param root TreeNode类 * @return int整型vector<vector<>> */
    void printnode(TreeNode* root,vector<vector<int> > &ans, int layer){
   
        if(root==nullptr)
            return;
        if(ans.size()<=layer){
   
            ans.push_back(vector<int>());
        }
        ans[layer].push_back(root->val);
        
        printnode(root->left,ans,layer+1);
        printnode(root->right,ans,layer+1);
    }

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

题解1：广度优先遍历

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

/** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * }; */
class Solution {
   
public:
    /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param root TreeNode类 * @return int整型vector<vector<>> */
    vector<vector<int> > levelOrderBottom(TreeNode* root) {
   
        // write code here
        vector<vector<int> > ans;
        vector<TreeNode*> dq = {
   root};
        vector<TreeNode*> temp_dq;
        vector<int> 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算法构建树，找到后序排序中的结尾值，该值为当前树的根节点。根据根节点在中序遍历中的位置将中序遍历分为左子树和右子树的中序遍历数组，依次构建左子树与右子树。

/** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * }; */
class Solution {
   
public:
    /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param inorder int整型vector 中序遍历序列 * @param postorder int整型vector 后序遍历序列 * @return TreeNode类 */
    TreeNode* build(vector<int>& inorder, vector<int>& 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<int>& inorder, vector<int>& postorder) {
   
        // write code here
        TreeNode* node = build(inorder, postorder, 0, inorder.size()-1,  0,  postorder.size()-1);
        return node;
    }
};

从前序与中序遍历序列构造二叉树

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

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

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */
class Solution {
   
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
   
        TreeNode* head = build(inorder, preorder, 0, inorder.size()-1,  0,  preorder.size()-1);
        return head;
    }
    TreeNode* build(vector<int>& inorder, vector<int>& 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;
    }
};

修剪叶子

牛客链接：NC169 修剪叶子

递归判断，当该节点的儿子为叶子节点时，将其置位nullptr并返回。否则深度遍历左右儿子节点。

/** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * }; */
class Solution {
   
public:
    /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param root TreeNode类 * @return TreeNode类 */
    
    TreeNode* pruneLeaves(TreeNode* root) {
   
        // write code here
        if(root==nullptr)
            return root;
        if(root->left && root->left->right == nullptr && root->left->left == nullptr)
            return nullptr;
        if(root->right && root->right->right == nullptr && root->right->left == nullptr)
            return nullptr;
        root->left = pruneLeaves(root->left);
        root->right = pruneLeaves(root->right);
        return root;
    }
};

循环右移二叉树

牛客链接：NC146 循环右移二叉树

解法1： DFS深度优先遍历

对于每一层，我们获取他的儿子节点（包含空），递归的将他的儿子节点循环右移K个节点，确定到正确位置后，将其重新插入到父亲节点的合适位置。（递归处理的时候，记得不处理空儿子，儿子的儿子右移也不会移动到空儿子上，并且空儿子也没有儿子）

/** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * }; */
class Solution {
   
public:
    /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param root TreeNode类 * @param k int整型 * @return TreeNode类 */
    void bfs(vector<TreeNode*> fathers, vector<TreeNode*> sons, int k){
   
        if(sons.size() == 0)  //最后一层叶子节点的儿子节点不处理
            return;
        vector<TreeNode*> new_sons;   //获取当前儿子节点的儿子节点 ，以便递归处理
        for(int i =0 ;i<sons.size();++i){
   
            if(sons[i]){
   
                new_sons.push_back(sons[i]->left);
                new_sons.push_back(sons[i]->right);
            }
        }
        bfs(sons,new_sons,k);        //递归处理
        
        reverse(sons.begin(), sons.end());              //子节点处理完毕，将当前儿子的位置循环右移K个位置，调整到合适位置。
        reverse(sons.begin(), sons.begin()+k%sons.size());
        reverse(sons.begin()+k%sons.size(), sons.end());
        
        int temp = 0;                 //重新进行插入
        for(int i =0 ;i<fathers.size();++i){
   
            if(fathers[i]){
   
                fathers[i]->left = sons[temp];
                temp++;
                fathers[i]->right = sons[temp];
                temp++;
            }
        }
    }
    
    TreeNode* cyclicShiftTree(TreeNode* root, int k) {
   
        // write code here
        vector<TreeNode*> sons;
        sons.push_back(root->left);
        sons.push_back(root->right);
        bfs({
   root},sons,k);
        return root;
    }
};

解法2：

使用两个数组来表示父亲节点和儿子节点，并且每次将儿子旋转到对应位置后，将其放到正确位置后，在处理儿子和儿子的儿子的结点之间的问题。

/** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * }; */
class Solution {
   
public:
    /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param root TreeNode类 * @param k int整型 * @return TreeNode类 */
    TreeNode* cyclicShiftTree(TreeNode* root, int k) {
   
        // write code here
        vector<TreeNode*> fathers = {
   root};
        vector<TreeNode*> sons;
        vector<TreeNode*> temp;
        
        sons.push_back(root->left);
        sons.push_back(root->right);
        
        while(sons.size()>0){
   
            reverse(sons.begin(), sons.end());
            reverse(sons.begin(), sons.begin() + k%sons.size());
            reverse(sons.begin() + k%sons.size(), sons.end());
            
            for(int i = 0; i<sons.size();++i){
   
                if(sons[i])
                {
   
                    temp.push_back(sons[i]->left);
                    temp.push_back(sons[i]->right);
                } 
            }
            
            int idx = 0;
            for(int i = 0; i<fathers.size();++i){
   
                if(fathers[i])
                {
   
                    fathers[i]->left = sons[idx];
                    idx++;
                    fathers[i]->right = sons[idx];
                    idx++;
                } 
            }
            
            fathers = sons;
            sons = temp;
            temp.clear();
        }
        
    return root;
    }
};