img

zhanglin

A Coder

胖狗子修行之路

个人站

欢迎来到我的个人站~

【leetcode】算法题记录(101-110)

| 阅读：次

对称二叉树

在这里插入图片描述

解题思路，递归和迭代分别代表着深度搜索(DFS)和广度搜索(BFS)。

深度搜索用栈或递归，需要明白如何递归，因为判断是否镜像对称，所以在递归的时候需要交换节点的左右节点进行递归。

广度搜索用队列，利用队列获得每一层的数字，其中在节点为null时也需要记录，然后判断该数组是否是一个回文串。

AC代码:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
 //BFS
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(root == NULL) return true;
        queue<TreeNode*> qtn;
        qtn.push(root);
        while(qtn.size() != 0) {
            int n = qtn.size();
            vector<int> vi;
            for(int i = 0; i < n; ++i) {
                TreeNode* ope = qtn.front();
                qtn.pop();
                if(ope->left) {
                    qtn.push(ope->left);
                    vi.push_back(ope->left->val);
                } 
                else vi.push_back(INT_MAX);
                if(ope->right) {
                    qtn.push(ope->right); 
                    vi.push_back(ope->right->val);
                } 
                else vi.push_back(INT_MAX);
            }
            vector<int> tmp = vi;
            reverse(vi.begin(), vi.end());
            if(tmp != vi) return false;
        }
        return true;
    }
};
//DFS
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if (root == nullptr) return true;
        return dfs(root->left, root->right);
    }

    bool dfs(TreeNode* root1, TreeNode* root2) {
        if (root1 == nullptr && root2 == nullptr) return true;
        if (root1 == nullptr || root2 == nullptr || root1->val != root2->val) return false;
        return dfs(root1->left, root2->right) && dfs(root1->right, root2->left);
    }
};

二叉树的层序遍历

在这里插入图片描述

解题思路，这道题的标签是中等，上一道题是简单。不清楚这个是按什么定位的。这道题就是利用队列对数进行bfs，也没有什么需要注意的问题。

AC代码:

/**
 * 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:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> res;
        if(root == NULL) return res;
        queue<TreeNode*> qtn;
        qtn.push(root);
        while(!qtn.empty()) {
            vector<int> vi;
            for(int n = qtn.size(); n > 0; --n) {
                TreeNode* ope = qtn.front();
                qtn.pop();
                vi.push_back(ope->val);
                if(ope->left) qtn.push(ope->left);
                if(ope->right) qtn.push(ope->right);
            }
            res.push_back(vi);
        }
        return res;
    }
};

二叉树的锯齿形层次遍历

在这里插入图片描述

解题思路，这道题和上一道题的方法一样，用 bfs 搜索实现层次遍历，设置一个标志位实现锯齿形。

AC代码:

/**
 * 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:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> res;
        if(root == NULL) return res;
        bool flag = false;
        queue<TreeNode*> qtn;
        qtn.push(root);
        while(!qtn.empty()) {
            vector<int> vi;
            for(int n = qtn.size(); n > 0; --n) {
                TreeNode* ope = qtn.front();
                qtn.pop();
                vi.push_back(ope->val);
                if(ope->left) qtn.push(ope->left);
                if(ope->right) qtn.push(ope->right);
            }
            if(flag) reverse(vi.begin(), vi.end());
            res.push_back(vi);
            flag = flag ^ 1;
        }
        return res; 
    }
};

二叉树的最大深度

在这里插入图片描述

解题思路，还是一样的 bfs，每遍历一次，深度加 1。也可以利用 dfs 遍历。

AC代码:

/**
 * 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:
    int maxDepth(TreeNode* root) {
        int res;
        if(root == NULL) return 0;
        queue<TreeNode*> qtn;
        qtn.push(root);
        while(!qtn.empty()) {
            for(int n = qtn.size(); n > 0; --n) {
                TreeNode* ope = qtn.front();
                qtn.pop();
                if(ope->left) qtn.push(ope->left);
                if(ope->right) qtn.push(ope->right);
            }
            ++res;
        }
        return res; 
    }
};
//dfs
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (root == nullptr) return 0;
        return max(maxDepth(root->left), maxDepth(root->right)) + 1;
    }
};

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

在这里插入图片描述

解题思路，利用递归的思想，构件根节点以及左右节点。

AC代码:

/**
 * 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 {
    unordered_map<int, int> index;
public:
    TreeNode* myBuildTree(const vector<int>& preorder, const vector<int>& inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right) {
        if (preorder_left > preorder_right) {
            return nullptr;
        }
        int preorder_root = preorder_left;
        int inorder_root = index[preorder[preorder_root]];

        TreeNode* root = new TreeNode(preorder[preorder_root]);

        int size_left_subtree = inorder_root - inorder_left;

        root->left = myBuildTree(preorder, inorder, preorder_left + 1, preorder_left + size_left_subtree, inorder_left, inorder_root - 1);
        root->right = myBuildTree(preorder, inorder, preorder_left + size_left_subtree + 1, preorder_right, inorder_root + 1, inorder_right);
        return root;
    }

    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if(preorder.size() != inorder.size()) return nullptr;
        int n = preorder.size();
        for (int i = 0; i < n; ++i) {
            index[inorder[i]] = i;
        }
        return myBuildTree(preorder, inorder, 0, n - 1, 0, n - 1);
    }
};

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

在这里插入图片描述

解题思路，和上一道题一样，利用递归构造的思想构造树。

AC代码:

/**
 * 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 {
    unordered_map<int, int> index;
public:
    TreeNode* myBuildTree(vector<int>& inorder, vector<int>& postorder, int inorder_l, int inorder_r, int postorder_l, int postorder_r) {
        if(inorder_l > inorder_r) return NULL;
        int postorder_root = postorder_r;
        int inorder_root = index[postorder[postorder_root]];
        TreeNode* root = new TreeNode(postorder[postorder_root]);
        int size_left = inorder_root - inorder_l;
        root->left = myBuildTree(inorder, postorder, inorder_l, inorder_root-1, postorder_l, postorder_l+size_left-1);
        root->right = myBuildTree(inorder, postorder, inorder_root+1, inorder_r, postorder_l+size_left, postorder_r-1);
        return root;
    }

    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        if(inorder.size() != postorder.size()) return NULL;
        int n = inorder.size();
        for(int i = 0; i < n; ++i) {
            index[inorder[i]] = i;
        }
        return myBuildTree(inorder, postorder, 0, n-1, 0, n-1);
    }
};

二叉树的层次遍历 II

在这里插入图片描述 解题思路，一样的使用队列进行广度搜索实现。

AC代码:

/**
 * 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:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        vector<vector<int>> res;
        queue<TreeNode* > qtn;
        if(root)qtn.push(root);
        while(qtn.size() != 0) {
            vector<int> tmp;
            for(int n = qtn.size(); n > 0; --n) {
                TreeNode* r = qtn.front(); qtn.pop();
                tmp.push_back(r->val);
                if(r->left) qtn.push(r->left);
                if(r->right) qtn.push(r->right);
            }
            res.insert(res.begin(),tmp);
        }
        return res;
    }
};

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

在这里插入图片描述

解题思路，这道题的答案不是唯一的，但是得清除平衡二叉搜索树的概念，如何去构造，首先想到的就是寻找中位数，然后递归寻找左右两边的中位数，这样就可以构造出一棵高度平衡的二叉搜索树。

AC代码:

/**
 * 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* findMid(vector<int>& nums, int start, int end) {
        if(start > end) return NULL;
        int mid = (end - start) / 2 + start;
        TreeNode* root = new TreeNode(nums[mid]);
        root->left = findMid(nums, start, mid-1);
        root->right = findMid(nums, mid+1, end);
        return root;
    }

    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return findMid(nums, 0, nums.size()-1);
    }
};

有序链表转换二叉搜索树

在这里插入图片描述 解题思路，简单一点的就是利用上一道题的思路，将链表转成数组，然后递归寻找中位数建树。为了不用同一种思路，后面借鉴了解题，解决这道题可以利用完全二叉树的思想，即父节点与其左右节点的关系建树。若父节点为 i ，则其左右节点为 2i 和 2i+1。利用这个性质就可以利用递归建树然后插入数实现完全平衡二叉树。

AC代码:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
/**
 * 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:
    ListNode* ope;
    TreeNode* transMid(int index, int n) {
        if(index>n) return nullptr;
        TreeNode* root = new TreeNode();
        root->left = transMid(index*2,n);
        if(ope == nullptr) return nullptr;
        root->val = ope->val;
        ope = ope->next;
        root->right = transMid(index*2+1,n);
        return root;
    }

    TreeNode* sortedListToBST(ListNode* head) {
        if(head == nullptr) return nullptr;
        ope = head;
        int len = 0;
        for(;head != nullptr; ++len, head = head->next);
        return transMid(1, len);
    }
};

平衡二叉树

在这里插入图片描述

解题思路，判断一棵树是否为平衡二叉树，关键在于遍历树的每个节点，然后判断该节点的左右子树的高度差的绝对值是不是大于1。

AC代码:

/**
 * 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:
    int maxDeep(TreeNode* root) {
        if (root == NULL) return 0;
        return max(maxDeep(root->left), maxDeep(root->right)) + 1;
    }
    bool isBalanced(TreeNode* root) {
        if(root == NULL) return true;
        queue<TreeNode*> qtn;
        qtn.push(root);
        while(!qtn.empty()) {
            for(int i = qtn.size(); i > 0; --i) {
                if(abs(maxDeep(qtn.front()->left) - maxDeep(qtn.front()->right)) > 1) return false;
                if(qtn.front()->left)qtn.push(qtn.front()->left);
                if(qtn.front()->right) qtn.push(qtn.front()->right);
                qtn.pop();
            }
        }
        return true;
    }
};

打赏一个呗

取消

感谢您的支持，我会继续努力的!

扫码支持
扫码支持
扫码打赏，你说多少就多少

打开支付宝扫一扫，即可进行扫码打赏哦