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

二叉树的后序遍历

牛客链接：NC192 二叉树的后序遍历

基础的递归操作，遵从 左子树->右子树->根节点存放的顺序进行遍历。

/**
 * 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
     */
    void postorder(TreeNode* root, vector<int> & ans){
        if(root == nullptr)
            return;
        postorder(root->left, ans);
        postorder(root->right, ans);
        ans.push_back(root->val);
    }
    vector<int> postorderTraversal(TreeNode* root) {
        // write code here
        vector<int>   ans;
        postorder(root,ans);
        return ans;
    }
};
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

二叉树的前序遍历

牛客链接：NC193 二叉树的前序遍历

同后序遍历，中序遍历也同理

/**
 * 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
     */
    void preorder(TreeNode* root, vector<int> & ans){
        if(root == nullptr)
            return;
        ans.push_back(root->val);
        preorder(root->left, ans);
        preorder(root->right, ans);
    }
    vector<int> preorderTraversal(TreeNode* root) {
        // write code here
        vector<int>   ans;
        preorder(root,ans);
        return ans;
    }
};
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

二叉树的中序遍历

牛客链接：NC161 二叉树的中序遍历

/**
 * 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
     */
    void inorder(TreeNode* root, vector<int> & ans){
        if(root == nullptr)
            return;
        inorder(root->left, ans);
        ans.push_back(root->val);
        inorder(root->right, ans);
        
    }
    vector<int> inorderTraversal(TreeNode* root) {
        // write code here
        vector<int>   ans;
        inorder(root,ans);
        return ans;
    }
};
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

二叉树的直径

牛客链接：NC195 二叉树的直径

采用深度遍历的算法，从底层向根节点开始计算寻找最大路径，对于每个节点，寻找左树最深路径和右树最深路径，求和即为最长路劲。对每个节点求最长路劲，选择最大的那个就是结果。
特别的，当遇到空结点时，返回-1，即之前节点为叶子节点，路径为0。

/**
 * 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 ans = 0;
    int dfs(TreeNode* root){
        if(root == nullptr)
            return -1;
        int left = dfs(root->left)+1;
        int right = dfs(root->right) + 1;
        ans = max(ans, left+right);
        return max(left, right);
    }
    int diameterOfBinaryTree(TreeNode* root) {
        // write code here
        dfs(root);
        return ans;
    }
};

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

二叉树的最大宽度

牛客链接：NC204 二叉树的最大宽度

解法1：DFS

我们假设初始根节点的位置为1，则对于每个在位置i的结点，若其左右子树存在，左子树的位置为2i，右子树的位置为2i+1。我们进行深度优先遍历，维护一个有关于树每层的最左和最右节点的位置矩阵，每层的宽度为其最右位置-最左位置+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<pair<int,int>> location;  //维护每层最左右位置的节点矩阵。
    void  bfs(TreeNode* root, int layer, int pos){
        if(location.size() < layer){
            location.push_back(pair<int,int>{pos,pos});   //每层初始化的位置就为最左节点的位置。
        }
        
        location[layer-1].second = max(pos, location[layer-1].second);  //维护每层最右位置的节点矩阵。
        
        if(root->left){
            bfs(root->left,layer+1,pos*2);
        }
        if(root->right){
            bfs(root->right,layer+1,pos*2+1);
        }
    }
    int widthOfBinaryTree(TreeNode* root) {
        // write code here
        if(root == nullptr)
            return 0;
        bfs(root, 1, 1);
        int ans = 1;
        
        for(pair<int, int> i: location)
        {
            ans = max(ans, i.second - i.first +1);  //查找所有层的宽度
        }
        return ans;
    }
};

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47

解法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 widthOfBinaryTree(TreeNode* root) {
        // write code here
        if (root == nullptr) {
            return 0;
        }
        
        queue<pair<TreeNode*, int>> q;
        q.push(make_pair(root, 1));
        int ans = 1;
        
        while(!q.empty()) {
            int size = q.size(), start = q.front().second;
            while(size--) {   //size用来保证该层的结点个数，当size=0时退出循环，该层遍历结束。
                auto cur = q.front();
                int index = cur.second;   //实时修改最优坐标。
                q.pop();
                
                if (cur.first->left != nullptr) {
                    q.push(make_pair(cur.first->left, cur.second * 2 ));
                }
                
                if (cur.first->right != nullptr) {
                    q.push(make_pair(cur.first->right, cur.second * 2 + 1));
                }
                
                ans = max(ans, index-start+1);  //每层结束，计算宽度。
            }
        }
        
        return ans;
    }
};
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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

二叉树的最小深度

牛客链接：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;
    }
};
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
34
35
36
37
38
39
40

解法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;
    }
};
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
34
35
36
37
38
39
40
41
42

从下到上打印二叉树

牛客链接：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
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
34
35
36
37

题解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;
    }
};
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
34
35
36
37
38
39
40
41
42
43

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

牛客链接：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;
    }
};
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
34
35

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

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;
    }
};
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

修剪叶子

牛客链接：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;
    }
};
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

循环右移二叉树

牛客链接：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;
    }
};
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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

解法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;
    }
};
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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

判断是不是二叉搜索树

牛客链接：NC184 判断是不是二叉搜索树

题解1：递归中序遍历

step 1：首先递归到最左，初始化maxLeft与pre。
step 2：然后往后遍历整棵树，依次连接pre与当前节点，并更新pre。
step 3：左子树如果不是二叉搜索树返回false。
step 4：判断当前节点是不是小于前置节点，更新前置节点。
step 5：最后由右子树的后面节点决定。

class Solution {
public:
    long pre = INT_MIN;
    //中序遍历
    bool isValidBST(TreeNode* root) {
        if(root == NULL)
            return true;
        //先进入左子树
        if(!isValidBST(root->left)) 
            return false;
        if(root->val <= pre)
            return false;
        //更新最值
        pre = root->val;  
        //再进入右子树
        if(!isValidBST(root->right))  
            return false;
        return true;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

解法2：

深度优先遍历，但是对于每个节点要考虑其取值范围。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @return bool布尔型
     */
    bool helper(TreeNode* root, long long lower, long long upper){
        if(root == nullptr)
            return true;
        if(root->val<=lower || root->val>=upper)
            return false;

        return helper(root->left,lower,root->val) && helper(root->right,root->val,upper);
    }
    bool isValidBST(TreeNode* root) {
        bool res = helper(root,LONG_MIN,LONG_MAX);
        return res;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

二叉搜索树的最近公共祖先

牛客链接:BM37 二叉搜索树的最近公共祖先

解法1：DFS

最后一个满足大于小值，小于大值的结点就是最近公共祖先。

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param root TreeNode类 
# @param p int整型 
# @param q int整型 
# @return int整型
#
class Solution:
    def lowestCommonAncestor(self , root: TreeNode, p: int, q: int) -> int:
        # write code here
        if root==None:
            return None
        if (p<=root.val and q>=root.val) or (p>=root.val and q<=root.val):
            return root.val
        if (p<root.val and q<root.val):
            return self.lowestCommonAncestor(root.left, p, q)
        if (p>root.val and q>root.val):
            return self.lowestCommonAncestor(root.right, p, q)
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

判断是不是完全二叉树

牛客链接:NC198 判断是不是完全二叉树

解法1：BFS

广度优先遍历每层，当读取到空节点的时候，剩余节点读取到非空，则不是完全二叉树。

/**
 * 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 bool布尔型
     */
    
    bool isCompleteTree(TreeNode* root) {
        // write code here
        if(!root)
            return true;
        deque<TreeNode*> arr{root};
        TreeNode* node;
        int flag = 1;
        while(arr.size()!=0){
            int n = arr.size();
            int i = 0;
            while(i<n){   //每层遍历
                node = arr[0];
                arr.pop_front();
                if(flag == 1 && node!=nullptr)  //没读到空节点，该节点不为空
                {
                    arr.push_back(node->left);
                    arr.push_back(node->right);
                }
                else if (flag == 0 && node!=nullptr)  //读到过空节点，该节点不为空
                    return false;
                else{                  //第一次读取空节点
                   flag = 0;
                }
                ++i;
            }
        }
        return true;
    }
};
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
34
35
36
37
38
39
40
41
42
43
44
45
46
47

二叉树的个数

牛客链接：NC150 二叉树的个数

解法1：DFS （超时）

n = 0时，就一种；n=1或2的时候也就一种；
当n=3或以上的时候，我们以其中的第i个节点为的结点为根节点，那么对于n个节点有n-i个节点在右子树，i-1个节点在左子树。
统计所有可能性。
假设n=3；那么对于以1为根节点的情况有两种，即2，3都在右子树上；以2为根节点的情况有1种，1在右子树，3在左子树；以3为根节点的情况有两种，1,2都在左子树。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 计算二叉树个数
     * @param n int整型 二叉树结点个数
     * @return int整型
     */
    int mod = 1000000007;
    int numberOfTree(int n) {
        // write code here
        if( n==0)
            return 1;
        if(n==1 or n==2)
            return n;
        int count = 0;
        for(int i=1;i<=n;++i){
            count += numberOfTree(n-i)*numberOfTree(i-1);  //以i为根节点，进行左右子树区分
            count %= mod;
        }
        return count;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

解法2：动态规划

传统的深度优先遍历会超时是因为有很多计算都重复进行了，我们这里完全可以将已经计算的结果保存起来，避免了重复计算的结果。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 计算二叉树个数
     * @param n int整型 二叉树结点个数
     * @return int整型
     */
    int mod = 1000000007;
    int numberOfTree(int n) {
        // write code here
        vector<long long> dp(n+1);
        dp[0] = 1;
        dp[1] = 1;
        dp[2] = 2;
        for(int i = 3;i<=n;++i){
            for(int j =1;j<=i;++j){
                dp[i] += (dp[i-j]*dp[j-1]);
                dp[i] %= mod;
            }
        }
        return (int)dp[n];
    }
};
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

将二叉搜索树改为累加树

牛客链接：将二叉搜索树改为累加树

二叉搜索树的性质可以得到该树的中序遍历时候每个节点的值为单调递增的，我们需要做的是从后往前，给每个节点加上其中序遍历右边节点的累加和就可以了。因此可以定义一个全局变量，表示从右到左时候，已经求得的累加和，当前节点就为累加和的值。

题解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 TreeNode类
     */
    int sum = 0;
    
    TreeNode* convertBST(TreeNode* root) {
        // write code here
        if(root == nullptr)
            return nullptr;
        stack<TreeNode*> tree;
        TreeNode *p = root;
        while(!tree.empty() || p != nullptr){   //按照中序遍历，先处理最右节点，顺便更新累加值。
            if(p!=nullptr)
            {
                tree.push(p);
                p = p->right;
            }
            else{
                p = tree.top();   //当右节点为空，则寻找左节点的最右节点。
                tree.pop();
                sum += p->val;
                p->val = sum;
                p = p->left;
            }
        }
        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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

解法2：DFS

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return TreeNode类
     */
    int sum = 0;
    void dfs(TreeNode* root){
        if(root == nullptr)
            return;
        dfs(root->right);
        sum+=root->val;
        root->val = sum;
        dfs(root->left);
    }
    TreeNode* convertBST(TreeNode* root) {
        // write code here
        dfs(root);
        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