SamJ's blog

leetcode 做题记录(8)

algorithm
Word count: 1.4kReading time: 6 min
2021/04/12 Share

剑指 Offer 26. 树的子结构

难度中等154

输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)

B是A的子结构， 即 A中有出现和B相同的结构和节点值。

返回 true，因为 B 与 A 的一个子树拥有相同的结构和节点值。

示例 1：

1
2
输入：A = [1,2,3], B = [3,1]
输出：false

示例 2：

1
2
输入：A = [3,4,5,1,2], B = [4,1]
输出：true

限制：

1
0 <= 节点个数 <= 10000

一开始想的也是递归，但是没想到是双重递归。。。就没想出来，又看了题解，分两层来考虑，确实很容易理解。

外面的是递归找匹配根节点的，找到了之后就掉另一个递归看结构是否匹配。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSubStructure(TreeNode* A, TreeNode* B) {
        if(A == nullptr || B == nullptr) return false;
        if(A->val == B->val && recur(A, B)) return true;    //从根开始匹配
        return isSubStructure(A->left, B) || isSubStructure(A->right, B);   //前序遍历A树，在其中找B树
    }

    bool recur(TreeNode* A, TreeNode* B){   //考虑到A和B已经匹配
        if(B == nullptr) return true;
        if(A == nullptr || A->val != B->val) return false;
        return recur(A->left, B->left) && recur(A->right, B->right);
    }
};

剑指 Offer 27. 二叉树的镜像

难度简单86

请完成一个函数，输入一个二叉树，该函数输出它的镜像。

例如输入：

1
2
3
4
5
   4 
  /  \ 
 2    7
/ \  / \
1 3  6  9

镜像输出：

1
2
3
4
5
   4  
  /  \ 
 7   2 
/ \  / \
9  6 3  1

示例 1：

1
2
输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]

限制：

1
0 <= 节点个数 <= 1000

两种方式，一种递归，还有一种是用栈实现。

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* mirrorTree(TreeNode* root) {
        if (root == NULL)   return NULL; 
        mirrorTree(root->left);
        mirrorTree(root->right);
        swap(root->left, root->right);
        return root;        
    }
};

//栈
class Solution {
public:
    TreeNode* mirrorTree(TreeNode* root) {
        stack<TreeNode*> s;
        s.push(root);
        
        while(!s.empty())
        {
            TreeNode *p = s.top();      //保存子树的根节点
            s.pop();
            if(p)
            {
                if(p->left  != NULL) s.push(p->left);
                if(p->right != NULL) s.push(p->right);
                swap(p->left,p->right);
            }
        }
        return root;
    }
};

剑指 Offer 28. 对称的二叉树

难度简单107

请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。 [1,2,2,null,3,null,3] 则不是镜像对称的。

示例 1：

1
2
输入：root = [1,2,2,3,4,4,3]
输出：true

示例 2：

1
2
输入：root = [1,2,2,null,3,null,3]
输出：false

也想到是递归，跟上面的差不太多。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(root == nullptr) return true;
        return recur(root->left, root->right);	//进入判断函数
    }

    bool recur(TreeNode* left, TreeNode* right) {
        if(left == nullptr && right == nullptr) return true;//同时到达空为true
        else if(left == nullptr||right == nullptr) return false;//只有一个空是false
        return (left->val == right->val) && recur(left->left, right->right) && recur(left->right, right->left);//左子树左孩子和右子树右孩子比，左子树右孩子和右子树左孩子比(镜像含义)。
    }
};

剑指 Offer 29. 顺时针打印矩阵

难度简单161

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。

示例 1：

1
2
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]

示例 2：

1
2
输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出：[1,2,3,4,8,12,11,10,9,5,6,7]

限制：

  • 0 <= matrix.length <= 100
  • 0 <= matrix[i].length <= 100

逻辑问题。

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
class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        if(!matrix.size()) return {};
        int l = 0, r = matrix[0].size() - 1, t = 0, b = matrix.size() - 1;
        vector<int> res;
        while(true)
        {
            for(int i = l; i <= r; ++i){        //往右走
                res.push_back(matrix[t][i]);
            }
            if(++t > b) break;
            for(int i = t; i <= b; ++i){        //往下走
                res.push_back(matrix[i][r]);
            }
            if(--r < l) break;
            for(int i = r; i >= l; --i){        //往左走
                res.push_back(matrix[b][i]);
            }
            if(--b < t) break;
            for(int i = b; i >= t; --i){        //往上走
                res.push_back(matrix[i][l]);
            }
            if(++l > r) break;
        }
        return res;
    }
};

剑指 Offer 30. 包含min函数的栈

难度简单70

定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。

示例:

1
2
3
4
5
6
7
8
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.min();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.min();   --> 返回 -2.

提示：

  1. 各函数的调用总次数不超过 20000 次

用辅助栈记录到达当前位置的栈中的最小值。

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
class MinStack {
public:
    /** initialize your data structure here. */
    stack<int> s;
    stack<int> mins;

    MinStack() {
        
    }
    
    void push(int x) {
        if(s.empty())
        {
            mins.push(x);
        }
        else
        {
            if(x <mins.top()) mins.push(x);
            else mins.push(mins.top());
        }
        s.push(x);
    }
    
    void pop() {
        s.pop();
        mins.pop();
    }
    
    int top() {
        return s.top();
    }
    
    int min() {
        
        return mins.top();
    }
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(x);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->min();
 */
CATALOG
  1. 1. 剑指 Offer 26. 树的子结构
  2. 2. 剑指 Offer 27. 二叉树的镜像
  3. 3. 剑指 Offer 28. 对称的二叉树
  4. 4. 剑指 Offer 29. 顺时针打印矩阵
  5. 5. 剑指 Offer 30. 包含min函数的栈
Total : 27
2021
2019
C++ paper hexo algorithm algorithm,c++ linux, C japanese,anime