代码探险家

这个屌丝很懒，什么也没留下！

热门标签

Leetcode 树专题题型总结_leetcode中关于树的题

作者：代码探险家 | 2024-07-05 01:55:29

踩

leetcode中关于树的题

二叉树

普通题型：

LeetCode 94. 二叉树的中序遍历

解题思路：递归 / 迭代

1.递归

class Solution {
private:
    vector<int>ans;
public:
    void Traversal(TreeNode* root){
        if(root==nullptr)
            return;
        Traversal(root->left);
        ans.push_back(root->val);
        Traversal(root->right);
    } 
    vector<int> inorderTraversal(TreeNode* root) {
        //递归终止条件
        if(root==nullptr)
            return ans;
        Traversal(root);
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

2.迭代【速度比递归慢】

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> stk;
        while (root != nullptr || !stk.empty()) {
            while (root != nullptr) {
                stk.push(root);
                root = root->left;
            }
            root = stk.top();
            stk.pop();
            res.push_back(root->val);
            root = root->right;
        }
        return res;
    }
};

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

101. 对称二叉树

解题思路：递归

class Solution {
public:
    bool check(TreeNode* right,TreeNode* left)
    {
        if(right==nullptr && left==nullptr) return true;
        if(right==nullptr || left==nullptr) return false;
        return right->val==left->val && check(right->left,left->right) && check(right->right,left->left);
    }
    bool isSymmetric(TreeNode* root) {
        return check(root,root);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12

102. 二叉树的层序遍历

解题思路：广度优先搜索（利用队列）

1.广度优先搜索即可，比较简单，很常规的解法。

//广度优先搜索
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>>ans;
        if(root==nullptr)
            return ans;
        queue<TreeNode*>q;
        q.push(root);//先把根节点放进去
        while(!q.empty())
        {
            int size=q.size();//当前要返回答案的大小
            vector<int>tempans;
            for(int i=0;i<size;i++)//踢出一个节点并往里面塞它的儿子们
            {
                TreeNode *temproot=q.front();
                if(temproot->left!=nullptr)
                    q.push(temproot->left);
                if(temproot->right!=nullptr)
                    q.push(temproot->right);
                tempans.push_back(temproot->val);
                q.pop();
            }
            ans.push_back(tempans);
        }
        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

vector二维数组的插入元素方法

若想定义A = [[0,1,2],[3,4]]，有两种方法。

（1）定义vector B分别为[0,1,2]和[3,4]，然后放入vector A。

vector A;

vector B;
B.push_back(0);
B.push_back(1);
B.push_back(2);

A.push_back(B);

B.clear();
B.push_back(3);
B.push_back(4);

A.push_back(B);

（2）
vector A;
for(int i = 0; i < 2; ++i) A.push_back(vector());
A[0].push_back(0);
A[0].push_back(1);
A[0].push_back(2);
A[1].push_back(3);
A[1].push_back(4);

LeetCode 104. 二叉树的最大深度

解题思路：深度优先搜索（递归）

class Solution {
public:
    int maxDepth(TreeNode* root) {
        //递归终止条件
        if(root==nullptr)
            return 0;
        return max(maxDepth(root->left),maxDepth(root->right))+1;
    }
};
1
2
3
4
5
6
7
8
9

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

解题思路：递归

前序遍历的第一个结点一定是根节点.

递归：每一次递归其实都是找一个根节点，往里面输入前序中序的各自长度就可以，根节点靠递归函数自己找。

pindex是通过哈希表来找到的（更快）（也可以使用遍历）

class Solution {
    unordered_map<int,int>index;
public:

    TreeNode* CreateTree(vector<int>& preorder, vector<int>& inorder,int preleft,int        preright,int inleft,int inright)
    {
        if(preleft > preright || inleft > inright)
            return nullptr;
        int pindex = index[preorder[preleft]];//找到pindex
        TreeNode* root = new TreeNode(preorder[preleft]);
        root->left = CreateTree(preorder,inorder,preleft+1,preleft-inleft+pindex,inleft,pindex-1);
        root->right = CreateTree(preorder,inorder,preleft-inleft+pindex+1,preright,pindex+1,inright);
        return root;
    }

    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int preleft = 0;
        int preright = preorder.size()-1;
        int inleft = 0;
        int inright = inorder.size()-1;
        for(int i=0;i<inorder.size();i++)
            index[inorder[i]]=i;//下标和值对应 方便以后找中序遍历的根节点
        return CreateTree(preorder,inorder,preleft,preright,inleft,inright);
    }
   
};
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

LeetCode 114. 二叉树展开为链表

解题思路：前序遍历

因为链表的顺序和前序遍历的顺序是一样的，所以用前序遍历把每个节点储存下来，再放到单链表中即可

class Solution {
private:
    vector<TreeNode*>pre;
public:
    //前序遍历
    void preTraversal(TreeNode* root){
        if(root==nullptr)
        {
            pre.push_back(root);
            return;
        }    
        pre.push_back(root);
        preTraversal(root->left);
        preTraversal(root->right);
    }
    
    void flatten(TreeNode* root) {
        preTraversal(root);
        root=pre[0];
        for(int i=1;i<pre.size();i++)
        {
            if(pre[i]!=nullptr)
            {
                root->right=pre[i];
                root->left=nullptr;
                root=root->right; 
            }  
        }    
    }
};
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

LeetCode 543. 二叉树的直径

解题思路：递归

class Solution {
    int ans=1;
public:
    int maxLength(TreeNode* root)
    {
        if(root==nullptr)
            return 0;
        int Lleft = maxLength(root->left);//左子树的最大深度
        int Lright = maxLength(root->right);//右子树最大深度
        ans = max(Lleft+Lright+1,ans);//更新答案

        return max(Lleft,Lright)+1;//返回的是两子树中取最大深度
    }

    int diameterOfBinaryTree(TreeNode* root) {
        //要记录每个结点延伸下去的左右子树的最大长度
        maxLength(root);
        return ans-1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

二叉搜索树

LeetCode 96. 不同的二叉搜索树

解题思路：二叉搜索树序列的个数与其值无关，只与区间长度有关

抄的leetcode

class Solution {
public:
    int numTrees(int n) {
        vector<int> G(n + 1, 0);
        G[0] = 1;
        G[1] = 1;

        for (int i = 2; i <= n; ++i) {
            for (int j = 1; j <= i; ++j) {
                G[i] += G[j - 1] * G[i - j];
            }
        }
        return G[n];
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

LeetCode 98. 验证二叉搜索树

class Solution {
public:
    bool helper(TreeNode* root, long long lower, long long upper) {
        if (root == nullptr) {
            return true;
        }
        //判断根节点是否在(lower,upper)的范围内
        //如果不在
        if (root -> val <= lower || root -> val >= upper) {
            return false;
        }
        //继续判断左节点，同时更新(lower,root->val)   // 继续判断右节点，同时更新(root->val,upper)
        return helper(root -> left, lower, root -> val) && helper(root -> right, root -> val, upper);
    }
    bool isValidBST(TreeNode* root) {
        return helper(root, LONG_MIN, LONG_MAX);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

基于树的DFS

LeetCode 236. 二叉树的最近公共祖先

解题思路：记录每个结点的父节点，然后一直p回溯往上走到根节点，期间用哈希表来标记走过的结点，之后q也一直往上走，当走到第一个p之前已经走过的结点时，这个结点就是最近公共祖先。

class Solution {
    unordered_map<TreeNode*,TreeNode*>parent;
    unordered_map<TreeNode*,int>visit;
public:

    TreeNode* Traversal(TreeNode* root)
    {
        if(root==NULL)
            return NULL;
        if(root->left!=NULL)
        {
            parent[root->left]=root;
            Traversal(root->left);
        }
        if(root->right!=NULL)
        {
            parent[root->right]=root;
            Traversal(root->right);
        }
        return NULL;
    }
    
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        Traversal(root);
        parent[root]=NULL;
        if(p==q)
            return p;
        TreeNode *pparent=p;
        TreeNode *qparent=q;

        while(pparent!=NULL)
        {
            visit[pparent]=1;//标记为访问过
            pparent=parent[pparent];
        }
        while(qparent!=NULL&&visit[qparent]!=1)
        {
            qparent=parent[qparent];
        }
        return qparent;
    }
};

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

226. 翻转二叉树

解题思路：很简单的遍历

class Solution {
public:
    void Traversal(TreeNode *root)
    {
        if(root==nullptr)
            return;
        if(root->left!=nullptr&&root->right!=nullptr)
        {
            TreeNode *temp=root->left;
            root->left=root->right;
            root->right=temp;
        }
        else if(root->left==nullptr)
        {
            root->left=root->right;
            root->right=nullptr;
            
        }
        else if(root->right==nullptr)
        {
            root->right=root->left;
            root->left=nullptr;
        }
        Traversal(root->left);
        Traversal(root->right);

    }
    TreeNode* invertTree(TreeNode* root) {
        //对于每个根节点都交换左右结点
        Traversal(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
25
26
27
28
29
30
31
32
33

951. 翻转等价二叉树

class Solution {
public:
//对任意结点，root1和root2有  1左=2左且1右=2右   或    1左=1右且1右=1左 就满足了
//
    bool flipEquiv(TreeNode* root1, TreeNode* root2) {
        if(!root1&&!root2)//如果都是空的
            return true;
        else if((!root1&&root2)||(root1&&!root2)||(root1->val!=root2->val))//只有一个是空的或则值不相同
            return false;
        return (flipEquiv(root1->left,root2->left)&&flipEquiv(root1->right,root2->right))||(flipEquiv(root1->left,root2->right)&&flipEquiv(root1->right,root2->left));
        
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

987. 二叉树的垂序遍历

class Solution {
    //往左走是 x+1 y-1  往右走是 x+1 y+1
    //列指的是y  
    //要判断有没有同行同列的
                //列对应的vector
    unordered_map<int,vector<int>>hash;
    unordered_map<int,int>X;
    vector<vector<int>>ans;
    int maxy=0,miny=0;
public:
//自己设置一个vector sort的函数
//sort: 如果这2个结点的x和y值都相同
//那么比较这两个结点的大小，把小的放到前面
//那就需要记录结点的x值和y值了
    void Traversal(TreeNode* Node,int x,int y){
        if(Node==nullptr)
            return;

        if(y>maxy)
            maxy=y;
        if(y<miny)
            miny=y;

        hash[y].push_back(Node->val);
        //记录下结点的x坐标
        X[Node->val]=x;

        if(Node->left!=nullptr)
            Traversal(Node->left,x+1,y-1);
        if(Node->right!=nullptr)
            Traversal(Node->right,x+1,y+1);
    }

    vector<int> Sort(vector<int> num){
        for(int i=0;i<num.size();i++){
            for(int j=i+1;j<num.size();j++){
                if(X[num[i]]==X[num[j]] && num[i]>num[j] || X[num[i]]>X[num[j]]){
                    int temp;
                    temp=num[i];
                    num[i]=num[j];
                    num[j]=temp;
                }

            }
        }   
        return num;
    }
    
    vector<vector<int>> verticalTraversal(TreeNode* root) {
        Traversal(root,0,0);
        for(int i=miny;i<=maxy;i++){
            if(hash.count(i)){
                hash[i]=Sort(hash[i]);
                ans.push_back(hash[i]);
            }    
        }
        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
50
51
52
53
54
55
56
57
58
59

572. 另一棵树的子树

    bool isSameTree(TreeNode* root1,TreeNode* root2)
    {
        //都是空的
        if(!root1&&!root2)
            return true;
        else if((root1&&!root2)||(!root1&&root2)||(root1->val!=root2->val))
            return false;
        return isSameTree(root1->left,root2->left)&&isSameTree(root1->right,root2->right);
    }

    bool isSubtree(TreeNode* root1, TreeNode* root2) {
    if (!root1 || !root2)
        return false;
    if (isSameTree(root1, root2))
        return true;
    return isSubtree(root1->left, root2) || isSubtree(root1->right, root2);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

863. 二叉树中所有距离为 K 的结点

class Solution {
    vector<int>ans;
    unordered_map<int,TreeNode*>parents;

public:
    void findParents(TreeNode* node) 
    {
        if (node->left != nullptr) 
        {
            parents[node->left->val] = node;
            findParents(node->left);
        }
        if (node->right != nullptr) 
        {
            parents[node->right->val] = node;
            findParents(node->right);
        }
    }

    void Go(TreeNode* target,TreeNode* from,int depth,int k)//DFS
    {
        if(target==nullptr)
            return;
        if(depth==k)
        {
            ans.push_back(target->val);
            return;
        }
        //from是防止走回头路
        if(target->left!=from) //往左走
            Go(target->left,target,depth+1,k);
        if(target->right!=from)//往右走
            Go(target->right,target,depth+1,k);
        if(parents[target->val]!=from)//往上走
            Go(parents[target->val],target,depth+1,k);
    }

    vector<int> distanceK(TreeNode* root, TreeNode* target, int k) {
        findParents(root);
        Go(target,nullptr,0,k);
        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

230. 二叉搜索树中第K小的元素

class Solution {
    vector<int>ans;
public:
    void Traversal(TreeNode* root)
    {
        if(root==nullptr)
            return;
        Traversal(root->left);
        ans.push_back(root->val);
        Traversal(root->right);
    }
    
    int kthSmallest(TreeNode* root, int k) {
        Traversal(root);
        return ans[k-1];
        
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

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

class Solution {
    unordered_map<TreeNode*,TreeNode*>parents;
    unordered_set<TreeNode*>visited;
public:
    void FindParents(TreeNode* root){
        if(root==NULL)
            return;
        if(root->left!=NULL){
            parents[root->left]=root;
            FindParents(root->left);
        }
        if(root->right!=NULL){
            parents[root->right]=root;
            FindParents(root->right);
        }
    }

    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        FindParents(root);
        parents[root]=NULL;
        TreeNode* temp=p;
        while(parents[temp]!=NULL){   //没到根节点，就一直做这个循环
            visited.insert(temp);
            temp=parents[temp];
        }
        temp=q;
        while(parents[temp]!=NULL){
            if(visited.count(temp))
                return temp;
            temp=parents[temp];
        }
        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

669. 修剪二叉搜索树

class Solution {
public:
    TreeNode* trimBST(TreeNode* root, int low, int high) {
        if(root==nullptr)
            return root;
        if(root->val>high) 
            return trimBST(root->left,low,high);
        if(root->val<low)
            return trimBST(root->right,low,high);
        root->left = trimBST(root->left,low,high);
        root->right = trimBST(root->right,low,high);
        return root;
    }  
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

700. 二叉搜索树中的搜索

class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        if(root==nullptr)
            return nullptr;
        if(root->val==val)
            return root;
        if(root->val>val)
            return searchBST(root->left,val);
        if(root->val<val)
            return searchBST(root->right,val);
        return nullptr;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

108. 将有序数组转换为二叉搜索树

class Solution {
public:
    TreeNode* CreateTree(vector<int>& nums,int left,int right){

        if(left>=right)//终止条件
            return nullptr;
        int mid=(right+left)/2;
        TreeNode* root = new TreeNode(nums[mid]);
        root->left=CreateTree(nums,left,mid);       //左子树
        root->right=CreateTree(nums,mid+1,right);   //右子树
        return root;
    }

    TreeNode* sortedArrayToBST(vector<int>& nums) {
        int n=nums.size();
        TreeNode* root;
        root=CreateTree(nums,0,n);
        return root;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

617. 合并二叉树

class Solution {
public:
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        if(root1==nullptr)
            return root2;
        if(root2==nullptr)
            return root1;
        TreeNode *merged = new TreeNode(root1->val+root2->val);
        merged->left = mergeTrees(root1->left,root2->left);
        merged->right = mergeTrees(root1->right,root2->right);
        return merged;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

基于树的BFS

103. 二叉树的锯齿形层序遍历

class Solution {
    vector<vector<int>>ans;
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        if(root==nullptr)
            return ans;
        queue<TreeNode*>q;
        int flag=0;
        q.push(root);//根节点入队
        while(!q.empty()){//q是非空的
            int n=q.size();
            vector<int>tempans;
            for(int i=0;i<n;i++){
                TreeNode *temproot=q.front();
                q.pop();
                if(temproot->left!=nullptr)
                    q.push(temproot->left);
                if(temproot->right!=nullptr)
                    q.push(temproot->right);
                tempans.push_back(temproot->val);
            }
            if(flag==1){
                reverse(tempans.begin(),tempans.end());
                flag=0;
            }
            else{
                flag=1;
            }
            ans.push_back(tempans);
        }
        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

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/代码探险家/article/detail/788849

Leetcode 树专题题型总结_leetcode中关于树的题

目录

二叉树

二叉搜索树

基于树的DFS

基于树的BFS