《LeetCode》数据结构入门板块（下）-阿里云开发者社区

第7天链表

141. 环形链表【简单，哈希表，双指针】

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-J1ekkkQj-1636886665428)(C:\Users\14051\AppData\Roaming\Typora\typora-user-images\image-20211114141050395.png)]

题目意思：给你链表判断是否有环

思路一：哈希表

class Solution {
public:
  //哈希表
  //时间复杂度：O(n)  
  //空间复杂度：O(n)   多余容器空间
  bool hasCycle(ListNode* head) {
    unordered_set<ListNode*> res;
    while (head != nullptr) {    //1.哈希表存结点，判断当前需要存储的结点，哈希表中是否存在；存在则有环
      if (res.count(head)) {
        return true;
      }
      res.insert(head);       
      head = head->next;     //实现结点的移动
    }
    return false;
  }
};

思路二：双指针

class Solution {
public:
  //一快一慢双指针  
  //时间复杂度：O(N)  一个while循环
  //空间复杂度：O(1)  两个指针空间 
  bool hasCycle(ListNode* head) {
    //特殊情况  长度为0 or 1
    if (head == nullptr || head->next == nullptr) {
      return false;
    }
    ListNode* slow = head;
    ListNode* fast = head->next;
    while (fast->next != nullptr) {   //两相邻指针，  若fast指针跑到slow后面去了  则有环
      fast = fast->next;
      slow = slow->next;
      if (slow >= fast) {   //为啥这句能成功？
        return true;
      }
    }
    return false;
  }
};

我搞不懂那句大小判断怎么能实现，很神奇

正版双指针思路：https://leetcode-cn.com/problems/linked-list-cycle/solution/dai-ma-sui-xiang-lu-141-huan-xing-lian-b-h1jq/

class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode* fast = head;
        ListNode* slow = head;
        while(fast != NULL && fast->next != NULL) {
            slow = slow->next;               //慢指针走一步  快指针走两步  相遇证明有环
            fast = fast->next->next;
            if (slow == fast) return true;   // 快慢指针相遇，说明有环
        }
        return false;                       //能走到NULL说明就没环
    }
};

21. 合并两个有序链表【简单，迭代，递归】

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-CcsK9q1m-1636886665430)(C:\Users\14051\AppData\Roaming\Typora\typora-user-images\image-20211114152715617.png)]

思路一：递归

class Solution {
public:
    //递归
    //时间复杂度：O(m+n)
    //空间复杂度：O(m+n)
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        //排序两种极端情况
        if (l1 == nullptr)  return l2;
        else if (l2 == nullptr) return l1;
        //L1的当前结点更小
        else if (l1->val < l2->val) {
            l1->next = mergeTwoLists(l1->next, l2);
            return l1;
        }
        else {   //L2的当前结点更小
            l2->next = mergeTwoLists(l1, l2->next);
            return l2;
        }
    }
};

思路二：迭代

//迭代
//时间复杂度：O(m+n)
//空间复杂度：O(1)
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode* preHead = new ListNode(-1);   //在起始点前面多开辟一个结点
        ListNode* prev = preHead;
        while (l1 != nullptr && l2 != nullptr) {   //当两链表都没到尾端
            if (l1->val < l2->val) {       //l1的小
                prev->next = l1;
                l1 = l1->next;
            }
            else {                        //l2的小
                prev->next = l2;
                l2 = l2->next;
            }
            prev = prev->next;
        }
        // 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可
        prev->next = l1 == nullptr ? l2 : l1;
        return preHead->next;   //返回起始结点
    }
};

思路三：vector容器先存结点，在一个一个拿出来组合成新的链表

这是我想实现滴，只会写这个

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        //排序两种极端情况
        if (l1 == nullptr)  return l2;
        if (l2 == nullptr) return l1;
    vector<ListNode*> v;
    auto node1 = l1;
    auto node2 = l2;
    while (node1 != nullptr && node2 != nullptr) {  //1.容器存数
      if (node1->val < node2->val) {
        v.push_back(node1);
        node1 = node1->next;
      }
      else {
        v.push_back(node2);
        node2 = node2->next;
      }
    }
    //while (node1 != nullptr) {
    //  v.push_back(node1);
    //  node1 = node1->next;
    //}
    //while (node2 != nullptr) {
    //  v.push_back(node2);
    //  node2 = node2->next;
    //}
    ListNode* prehead = new ListNode(-1);  //生成head前面的一个结点
    auto temp_node = prehead;
    for (auto i : v) {                   //2.组合成新的链表
      temp_node->next = i;
      temp_node = temp_node->next;
    }
    //temp_node->next = NULL;
    //3. 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可
    temp_node->next = node1 == nullptr ? node2 : node1;
    return prehead->next;
    }
};

203. 移除链表元素【简单，迭代，递归】

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-wvdE8NZl-1636886665430)(C:\Users\14051\AppData\Roaming\Typora\typora-user-images\image-20211114155600668.png)]

思路一：递归

class Solution {
public:
    //递归
    ListNode* removeElements(ListNode* head, int val) {
        if (head == nullptr) {                         //判断是否为空链表
            return head;
        }
        head->next = removeElements(head->next, val);  //从第二个元素开始递归
        return head->val == val ? head->next : head;   //判断头结点是否等于val
    }
};

思路二：迭代

我能想到的是这个思路

做链表的思路都是要在head结点前面再生成一个结点；链表类型的题目一般都有两种解法：迭代和递归；然而递归都好难理解，写不出来。

class Solution {
public:
    //迭代
    ListNode* removeElements(ListNode* head, int val) {
        struct ListNode* dummyHead = new ListNode(0, head);  //生成一个结点，结点值为0，结点的下一个结点为head
        struct ListNode* temp = dummyHead;       //这个结点现在是head结点的前一个结点
        while (temp->next != NULL) {            //遍历后面的结点
            if (temp->next->val == val) {
                temp->next = temp->next->next;  //修改指针指向
            }
            else {
                temp = temp->next;
            }
        }
        return dummyHead->next;
    }
};

第8天链表

206. 反转链表【简单，双指针，栈】

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-2tvy3JuX-1636886665431)(C:\Users\14051\AppData\Roaming\Typora\typora-user-images\image-20211114162928209.png)]

思路一：栈

反转最适合栈

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        stack<int> sta;                       //1.先把所有的数存储栈中
        while (head != NULL) {
            sta.push(head->val);
            head = head->next;
        }
        ListNode* l_ans = new ListNode(-1);   //2.然后生成新的链表，一个一个数链接起来
        ListNode* l = l_ans;
        while (!sta.empty()) {
            l->next = new ListNode(sta.top());
            sta.pop();
            l = l->next;
        }
        return l_ans->next;
    }
};

栈其实也可以存结点ListNode*

思路二：使用双指针修改指向

class Solution {
public:
    //双指针实现修改指向  下一个指向前一个
    ListNode* reverseList(ListNode* head) {
        ListNode* fast = head;        //快指针指向头结点  慢指针指向头结点的前一个结点，即NULL
        ListNode* slow = NULL;
        while (fast != nullptr) {
            ListNode* next = fast->next;
            fast->next = slow;      //核心代码，修改指向
            slow = fast;            //前移两个指针
            fast = next;
        }
        return slow;
    }
};

83. 删除排序链表中的重复元素【简单】

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-wKAxCJRV-1636886665432)(C:\Users\14051\AppData\Roaming\Typora\typora-user-images\image-20211114163627675.png)]

思路：单次遍历，判断当前结点值是否与下一个结点值相等，是则删除下一结点

class Solution {
public:
  ListNode* deleteDuplicates(ListNode* head) {
    if (head == nullptr || head->next == nullptr) {   //排除极端情况
      return head;
    }
    ListNode* node = head;
    while (node->next != nullptr) {
      if (node->val == node->next->val) {
        node->next = node->next->next;      //删除下一个结点
      }
      else {
        node = node->next;
      }
    }
    return head;
  }
};

其他思路：unordered_set哈希表存储val，再生成新链表。

第9天栈/队列

20. 有效的括号【简单，栈】

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-O2GO1w8t-1636886665432)(C:\Users\14051\AppData\Roaming\Typora\typora-user-images\image-20211114164147065.png)]

思路：单调栈消消乐

class Solution04 {
public:
  bool isValid(string s) {
    int n = s.size();      //获取字符串长度
    if (n % 2 == 1) {      //1.字符串长度为奇数肯定错误
      return false;
    }
    stack<char> stk;
    map<char, char> pairs = {
      {')', '('},
      {']', '['},
      {'}', '{'}
    };
    for (int i = 0; i < n; i++) {
      if (s[i] == '(' || s[i] == '[' || s[i] == '{') {  //2.存入左括号
        stk.push(s[i]);
      }
      else {                                            //3.消除右括号
        if (stk.empty() || stk.top() != pairs[s[i]]) {  
          return false;                            //false    空栈  或者 右括号与左括号类型不匹配
        }
        stk.pop();
      }
    }
    return stk.empty();
  }
};

232. 用栈实现队列【简单，栈】

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-qd4dVP2d-1636886665433)(C:\Users\14051\AppData\Roaming\Typora\typora-user-images\image-20211114164522144.png)]

思路：用栈模拟队列，就是两个栈里面的数据倒来倒去

class MyQueue {
private:
    stack<int>  in_stack, out_stack;    //实现两个倒数的函数
    void in2out() {
        while (!in_stack.empty()) {   //in_stack非空
            out_stack.push(in_stack.top());
            in_stack.pop();
        }
    }
    void out2in() {
        while (!out_stack.empty()) {
            in_stack.push(out_stack.top());
            out_stack.pop();
        }
    }
public:
    MyQueue() {}
    void push(int x) {   //入队
        in_stack.push(x);
    }
    int pop() {                   //出队   即删除第一个入栈元素
        if (out_stack.empty()) {
            in2out();
        }
        int x = out_stack.top();
        out_stack.pop();          //即删除栈底部的数
        if (in_stack.empty()) {
            out2in();
        }
        return x;
    }
    int peek() {   //返回队列开头元素   即返回第一个入栈元素
        if (out_stack.empty()) {
            in2out();
        }
        int x = out_stack.top();
        if (in_stack.empty()) {
            out2in();
        }
        return x;
        //return out_stack.top();
    }
    bool empty() {  //判断队是否为空
        return in_stack.empty() && out_stack.empty();
    }
};

第10天树

144. 二叉树的前序遍历【简单】

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-gSotvDI6-1636886665434)(C:\Users\14051\AppData\Roaming\Typora\typora-user-images\image-20211114165026430.png)]

思路一：递归

时间复杂度：O(n)

空间复杂度：O(n)

思路链接：https://leetcode-cn.com/problems/binary-tree-preorder-traversal/solution/dai-ma-sui-xiang-lu-chi-tou-qian-zhong-hou-xu-de-d/

class Solution {
public:
    void preorder(TreeNode *root, vector<int> &res) {
        if (!root) return;
        res.push_back(root->val);    //中
        preorder(root->left, res);   //左
        preorder(root->right, res);  //右
    }
    vector<int> preorderTraversal(TreeNode *root) {
        vector<int> res;
        preorder(root, res);
        return res;
    }
};

思路二：迭代

时间复杂度：O(n)

空间复杂度：O(n)

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> ans;
        stack<TreeNode*> stk;
        if (root != NULL) {   //压入根结点
            stk.push(root);
        }
        while (!stk.empty()){  //入栈是 根右左
            TreeNode* cur = stk.top();
            stk.pop();
            ans.push_back(cur->val);                //中
            if (cur->right) stk.push(cur->right);   //由
            if (cur->left) stk.push(cur->left);     //左
        }
        return ans;
    }
};

94. 二叉树的中序遍历【简单】

思路一：递归

class Solution {
public:
    void inorder(TreeNode* root, vector<int> &res){
        if(!root) return;
        inorder(root->left, res);   //左
        res.push_back(root->val);   //中
        inorder(root->right, res);  //右
    }
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        inorder(root, res);
        return res;
    }
};

思路二：迭代

官方版本如下：

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

下面代码可能清晰一些

思路链接：https://leetcode-cn.com/problems/binary-tree-inorder-traversal/solution/dai-ma-sui-xiang-lu-che-di-chi-tou-qian-xjof1/

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> st;
        TreeNode* cur = root;
        while (cur != NULL || !st.empty()) {
            if (cur != NULL) { // 指针来访问节点，访问到最底层
                st.push(cur); // 将访问的节点放进栈
                cur = cur->left;                // 左
            } else {
                cur = st.top(); // 从栈里弹出的数据，就是要处理的数据（放进result数组里的数据）
                st.pop();
                result.push_back(cur->val);     // 中
                cur = cur->right;               // 右
            }
        }
        return result;
    }
};

145. 二叉树的后序遍历【简单】

思路一：递归

class Solution {
public:
    void postorder(TreeNode* root, vector<int> &res){
        if(!root){
            return;
        }
        postorder(root->left, res);
        postorder(root->right, res);
        res.push_back(root->val);
    }
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        postorder(root, res);
        return res;
    }
};

思路二：迭代

思路链接：https://leetcode-cn.com/problems/binary-tree-postorder-traversal/solution/bang-ni-dui-er-cha-shu-bu-zai-mi-mang-che-di-chi-t/

class Solution {
public:
    //后续迭代最难，有些结点反复进出栈
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        if (root == nullptr) {
            return res;
        }
        stack<TreeNode*> stk;
        TreeNode* prev = nullptr;
        while (root != nullptr || !stk.empty()) {
            while (root != nullptr) {
                stk.push(root);
                root = root->left;
            }
            root = stk.top();
            stk.pop();
            if (root->right == nullptr || root->right == prev) {
                res.push_back(root->val);
                prev = root;
                root = nullptr;
            }
            else {
                stk.push(root);
                root = root->right;
            }
        }
        return res;
    }
};

第11天树

102. 二叉树的层序遍历【中等，BFS】

这个很重要！！！后面很多题都是在广度优先遍历的基础上改

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector <vector <int>> ret;
        if (!root) return ret;    //排除空二叉树情况
        queue <TreeNode*> q;
        q.push(root);            //根结点入队
        while (!q.empty()) {
            int currentLevelSize = q.size();        //记录当前层的结点个数
            ret.push_back(vector <int>());  //这句重点
            for (int i = 1; i <= currentLevelSize; ++i) {
                auto node = q.front();             //获取队头元素
                q.pop();                           //删除队头元素
                ret.back().push_back(node->val);   //往ret的最后一个容器中压元素
                if (node->left) { 
                    q.push(node->left); 
                }
                if (node->right) {
                    q.push(node->right);
                }
            }
        }
        return ret;
    }
};

104. 二叉树的最大深度【简单，DFS，BFS】

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-PY8nehXF-1636886665436)(C:\Users\14051\AppData\Roaming\Typora\typora-user-images\image-20211114165932906.png)]

思路一：广度优先遍历

本题的广度优先遍历方法是在102. 二叉树的层序遍历的基础上修改返回值得到的

时间复杂度：O(n)

空间复杂度：O(n)

class Solution {
public:
    int maxDepth(TreeNode* root) {
        vector <vector <int>> ret;
        if (!root) return 0;    //排除空二叉树情况
        queue <TreeNode*> q;
        q.push(root);          //根结点入队
        while (!q.empty()) {
            int currentLevelSize = q.size();   //记录当前层的结点个数
            ret.push_back(vector <int>());
            for (int i = 1; i <= currentLevelSize; ++i) {   //队列弹出当前层所有元素并记录   并压入下一层所有元素
                auto node = q.front();            
                q.pop();                          
                ret.back().push_back(node->val);   //往ret的最后一个容器中压元素
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
        }
        return ret.size();   //与104题相比   只是修改了返回值
    }
};

其实vector <vector <int>> ret;容器是多余的，可以用一个int型遍历代替记录。优化如下：

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (!root) return 0;     //排除空二叉树情况
        queue <TreeNode*> q;
        q.push(root);    //根结点入队
        int res = 0;     //记录层数
        while (!q.empty()) {
            int currentLevelSize = q.size();   //记录当前层的结点个数
            for (int i = 1; i <= currentLevelSize; ++i) {  //队列弹出当前层所有元素   并压入下一层所有元素
                auto node = q.front();            
                q.pop();                          
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
            res++;
        }
        return res;
    }
};

思路二：深度优先搜索，递归套娃

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (root == nullptr) return 0;  //空二叉树情况  或者跳出该层的递归
        return max(maxDepth(root->left), maxDepth(root->right)) + 1;
    }
};

101. 对称二叉树【简单，BFS，DFS】

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-xpuELwDX-1636886665437)(C:\Users\14051\AppData\Roaming\Typora\typora-user-images\image-20211114170518855.png)]

思路一：补全儿子结点

给每个节点都补全左右儿子结点（如果没有的话），补的值为INT_MIN

之后用vector嵌套容器存储

再用双指针遍历每一层的第一个和倒数第一个，第二个和倒数第二个。。。值是否相等

此代码是在102. 二叉树的层序遍历基础上改的，方法为广度优先遍历

class Solution {
public:
  bool isSymmetric(TreeNode* root) {
    vector<vector<int>> v;
    if (!root) return true;
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
      int current_level_size = q.size();
      v.push_back(vector<int>());
      for (int i = 1; i <= current_level_size; i++) {
        auto node = q.front();
        q.pop();
        if (node) {
          v.back().push_back(node->val);
        }
        else {
          v.back().push_back(INT_MIN);
          continue;
        }
        if (node->left) {
          q.push(node->left);
        }
        else {
          q.push(nullptr);
        }
        if (node->right) {
          q.push(node->right);
        }
        else {
          q.push(nullptr);
        }
      }
    }
    for (int i = 1; i < v.size(); i++) {
      int n = v[i].size();   //每一层元素的个数
      int left = 0;
      int right = n - 1;
      for (left; left < n / 2; left++) {
        if (v[i][left] == v[i][right]) {
          right--;
        }
        else {
          return false;
        }
      }
    }
    return true;
  }
};

思路二：正经的迭代法

思路链接：https://leetcode-cn.com/problems/symmetric-tree/solution/dai-ma-sui-xiang-lu-dai-ni-xue-tou-er-ch-hnjo/

树的根结点不需要加入栈，我们直接把左子树和右子树入栈

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if (root == NULL) return true;
        queue<TreeNode*> que;
        que.push(root->left);   // 将左子树头结点加入队列
        que.push(root->right);  // 将右子树头结点加入队列
        while (!que.empty()) {  // 接下来就要判断这这两个树是否相互翻转
            TreeNode* leftNode = que.front(); que.pop();
            TreeNode* rightNode = que.front(); que.pop();
            if (!leftNode && !rightNode) {  // 左节点为空、右节点为空，此时说明是对称的
                continue;
            }
            // 左右一个节点不为空，或者都不为空但数值不相同，返回false
            if ((!leftNode || !rightNode || (leftNode->val != rightNode->val))) {
                return false;
            }
            que.push(leftNode->left);   // 加入左节点左孩子
            que.push(rightNode->right); // 加入右节点右孩子
            que.push(leftNode->right);  // 加入左节点右孩子
            que.push(rightNode->left);  // 加入右节点左孩子
        }
        return true;
    }
};

思路三：递归

链接，递归的思路可以看此链接，比官方答案要清晰很多

递归三部曲：

1.确定递归函数的参数和返回值

2.确定终止条件

3.确定单层递归的逻辑

class Solution {
public:
    bool compare(TreeNode* left, TreeNode* right) {
        // 首先排除空节点的情况
        if (left == NULL && right != NULL) return false;         
        else if (left != NULL && right == NULL) return false;
        else if (left == NULL && right == NULL) return true;
        // 排除了空节点，再排除数值不相同的情况
        else if (left->val != right->val) return false;
        // 此时就是：左右节点都不为空，且数值相同的情况
        // 此时才做递归，做下一层的判断
        bool outside = compare(left->left, right->right);   // 左子树：左、 右子树：右
        bool inside = compare(left->right, right->left);     // 左子树：右、 右子树：左
        bool isSame = outside && inside;                    // 左子树：中、 右子树：中 （逻辑处理）
        return isSame;
    }
    bool isSymmetric(TreeNode* root) {
        if (root == NULL) return true;
        return compare(root->left, root->right);
    }
};

第12天树

226. 翻转二叉树【简单，BFS，DFS】

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-eOGy0P28-1636886665438)(C:\Users\14051\AppData\Roaming\Typora\typora-user-images\image-20211114171736778.png)]

思路一：递归

具体可看此链接的解析：链接

//递归
class Solution {
public:
  TreeNode* invertTree(TreeNode* root) {
    if (root == NULL) return root;
    swap(root->left, root->right);  // 中
    invertTree(root->left);         // 左
    invertTree(root->right);        // 右
    return root;
  }
};

思路二：根据102. 二叉树的层序遍历修改，即广度优先遍历

//广度优先遍历
class Solution {
public:
  TreeNode* invertTree(TreeNode* root) {
    if (!root) return root;   //排除空二叉树情况
    queue <TreeNode*> q;
    q.push(root);        //根结点入队
    while (!q.empty()) {
      int currentLevelSize = q.size();   //记录当前层的结点个数
      for (int i = 1; i <= currentLevelSize; i++) {
        auto node = q.front();             
        q.pop();                           
        swap(node->left, node->right);     //交换   修改了这句
        if (node->left) q.push(node->left);
        if (node->right) q.push(node->right);
      }
    }
    return root;
  }
};

优化：分层其实不需要了

//优化  for循环其实没必要记录层数  省去
class Solution {
public:
  TreeNode* invertTree(TreeNode* root) {
    if (!root) return root;
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
      TreeNode* node = q.front();              
      q.pop();
      swap(node->left, node->right);
      if (node->left) q.push(node->left); 
      if (node->right) q.push(node->right);
    }
    return root;
  }
};

思路三：深度优先遍历

//同理 其实stack也能实现功能
//这里叫深度优先遍历  前序遍历
class Solution {
public:
  TreeNode* invertTree(TreeNode* root) {
    if (!root) return root;
    stack<TreeNode*> s;
    s.push(root);
    while (!s.empty()) {
      TreeNode* node = s.top();              // 中
      s.pop();
      swap(node->left, node->right);
      if (node->right) s.push(node->right);   // 右
      if (node->left) s.push(node->left);     // 左
    }
    return root;
  }
};

112. 路径总和【简单，栈，递归】

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-5k21rWiv-1636886665440)(C:\Users\14051\AppData\Roaming\Typora\typora-user-images\image-20211114172435557.png)]

思路一：迭代

stack和queue都能实现功能，差距只是在pop上

stack时间复杂度好点，毕竟栈头的结点与栈尾的结点相比更可能是叶子结点

class Solution {
public:
  bool hasPathSum(TreeNode* root, int targetSum) {
        if (!root) return false;
        stack<pair<TreeNode*, int>> s;
        s.push(make_pair(root, root->val));
        while (!s.empty()) {
            pair<TreeNode*, int> node = s.top();
            s.pop();
            // 如果该节点是叶子节点了，同时该节点的路径数值等于targetSum，那么就返回true
            if (!node.first->left && !node.first->right && targetSum == node.second) return true;
            //压入右节点
            if (node.first->right) s.push(make_pair(node.first->right, node.second + node.first->right->val));
            //压入左节点
            if (node.first->left) s.push(make_pair(node.first->left, node.second + node.first->left->val));
        }
        return false;
  }
};

上面代码的对组也可以用两个栈替换，一个栈记录结点，一个栈记录路径长度；官方答案就是这样的

思路二：递归

class Solution {
public:
    bool hasPathSum(TreeNode *root, int sum) {
        if (root == nullptr) {
            return false;
        }
        if (root->left == nullptr && root->right == nullptr) {
            return sum == root->val;
        }
        return hasPathSum(root->left, sum - root->val) ||
               hasPathSum(root->right, sum - root->val);
    }
};

第13天树

700. 二叉搜索树中的搜索【简单】

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-qodWkqVv-1636886665441)(C:\Users\14051\AppData\Roaming\Typora\typora-user-images\image-20211114172722451.png)]

主要是注意二叉搜索树的特点

思路一：迭代

//广度优先  层序遍历
class Solution {
public:
  TreeNode* searchBST(TreeNode* root, int val) {
    if (!root) return NULL;
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
      TreeNode* node = q.front();
      q.pop();
      if (node->val == val) {
        return node;
      }
      else {
        if (node->left) q.push(node->left);
        if (node->right) q.push(node->right);
      }
    }
    return NULL;
  }
};

优化：我们要注意到这是二叉搜索树，该树是有序的，左<中<右，因此可以在此特点上做优化

//二叉搜索树是一个有序数   左<中<右
class Solution {
public:
  TreeNode* searchBST(TreeNode* root, int val) {
    while (root) {
      if (root->val > val) root = root->left;         //结点值>目标值  在左子树
      else if (root->val < val) root = root->right;   //结点值<目标值  在右子树
      else return root;     //相等返回
    }
    return NULL;   //未搜索到，返回
  }
};

思路二：递归，感觉递归就靠玄学

class Solution {
public:
  TreeNode* searchBST(TreeNode* root, int val) {
    if (!root) return NULL;
    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 NULL;
  }
};

701. 二叉搜索树中的插入操作【中等】

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-yqivuESX-1636886665442)(C:\Users\14051\AppData\Roaming\Typora\typora-user-images\image-20211114182718727.png)]

思路对了就容易做！

思路：拿val与根结点值比大小，看从左走还是往右走

这是添加一个叶子结点的方法；原来的结点值不发生改变

一开始思路就想错了，我还以为原二叉树的结点值还有发生交换。

思路链接：https://leetcode-cn.com/problems/insert-into-a-binary-search-tree/solution/dai-ma-sui-xiang-lu-dai-ni-xue-tou-er-ch-o2pu/

class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        if (root == nullptr) {            //空树
            return new TreeNode(val);
        }
        TreeNode* pos = root;
        while (pos != nullptr) {
            if (val < pos->val) {   //val<当前结点  往左走
                if (pos->left == nullptr) {
                    pos->left = new TreeNode(val);
                    break;
                }
                else {
                    pos = pos->left;
                }
            }
            else {    //往右走
                if (pos->right == nullptr) {
                    pos->right = new TreeNode(val);
                    break;
                }
                else {
                    pos = pos->right;
                }
            }
        }
        return root;
    }
};

第14天

98. 验证二叉搜索树【中等】

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-VnmozmgT-1636886665443)(C:\Users\14051\AppData\Roaming\Typora\typora-user-images\image-20211114183036686.png)]

注意：二叉搜索树中序遍历是递增序列

思路一：递归

//思路：把结点值全部中序遍历装入容器  判断容器是否为升序排列
class Solution {
public:
    void inorder(TreeNode* root, vector<int>& res) {
        if (!root) return;
        inorder(root->left, res);   //左
        res.push_back(root->val);   //中
        inorder(root->right, res);  //右
    }
    bool isValidBST(TreeNode* root) {
        vector<int> res;
        inorder(root, res);
    for (int i = 1; i < res.size(); i++) {
      if (res[i] <= res[i - 1]) return false;
    }
    return true;
    }
};

思路二：迭代

在中序遍历的迭代版本上改进

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        stack<TreeNode*> st;
        TreeNode* cur = root;
        TreeNode* pre = NULL; // 记录前一个节点
        while (cur != NULL || !st.empty()) {
            if (cur != NULL) {
                st.push(cur);
                cur = cur->left;                // 左
            }
            else {
                cur = st.top();                 // 中
                st.pop();
                if (pre != NULL && cur->val <= pre->val)   //多了这句
                    return false;
                pre = cur;                                 //保存前一个访问的结点
                cur = cur->right;               // 右
            }
        }
        return true;
    }
};

653. 两数之和 IV - 输入 BST【简单，哈希表】

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-WYilX4gJ-1636886665444)(C:\Users\14051\AppData\Roaming\Typora\typora-user-images\image-20211114183526629.png)]

查找元素的题目就得用哈希表，哈希表有find()和count()函数

思路：哈希表+BFS

//查数就用哈希表
class Solution {
public:
  bool findTarget(TreeNode* root, int k) {
    unordered_set<int> s;
    queue<TreeNode*> q;       //BFS需要queue实现
    q.push(root);
    s.insert(root->val);
    while (!q.empty()) {
      auto node = q.front();
      q.pop();
      if (node->left) {
        q.push(node->left);
        if (s.count(k - node->left->val)) return true;  //查看哈希表中是否有另一元素  
        else s.insert(node->left->val);
      }
      if (node->right) {
        q.push(node->right);
        if (s.count(k - node->right->val)) return true;
        else s.insert(node->right->val);
      }
    }
    return false;
  }
};

思路二：递归+哈希表

class Solution {
public:
  bool find(TreeNode * cur, int k, unordered_set<int> &set){
    // 递归结束条件
    if (!cur) return false;                    // 情况一  遍历到空节点仍然没有找到符合条件的值
    if (set.count(k - cur->val)) return true;  // 情况二  符合条件
    // 递归本身
    set.insert(cur->val);
    return find(cur->left, k, set) || find(cur->right, k, set);
  }
  bool findTarget(TreeNode * root, int k){
    unordered_set<int> set;
    return find(root, k, set);
  }
};

235. 二叉搜索树的最近公共祖先【简单】

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-KfxNBkTV-1636886665445)(C:\Users\14051\AppData\Roaming\Typora\typora-user-images\image-20211114183845224.png)]

思路：两个结点qp，则它们的公共结点值会介于它们两值之间。方法全是基于这个思路。

思路一：递归

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root->val > p->val && root->val > q->val) {
            return lowestCommonAncestor(root->left, p, q);
        }
        else if (root->val < p->val && root->val < q->val) {
            return lowestCommonAncestor(root->right, p, q);
        }
        else return root;
    }
};

思路二：迭代

//牢记二叉搜索树特点
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        int min_val = min(q->val, p->val);
        int max_val = max(q->val, p->val);
        while (root) {
            if (root->val > max_val) root = root->left;        //大于最大的往左走
            else if (root->val < min_val) root = root->right;  //小于最小的往右走
            else return root;                                  //介于中间返回
        }
        return NULL;   //没查找到
    }
};

《LeetCode》数据结构入门板块（下）

第7天链表

141. 环形链表【简单，哈希表，双指针】

21. 合并两个有序链表【简单，迭代，递归】

203. 移除链表元素【简单，迭代，递归】

第8天链表

206. 反转链表【简单，双指针，栈】

83. 删除排序链表中的重复元素【简单】

第9天栈/队列

20. 有效的括号【简单，栈】

232. 用栈实现队列【简单，栈】

第10天树

144. 二叉树的前序遍历【简单】

94. 二叉树的中序遍历【简单】

145. 二叉树的后序遍历【简单】

第11天树

102. 二叉树的层序遍历【中等，BFS】

104. 二叉树的最大深度【简单，DFS，BFS】

101. 对称二叉树【简单，BFS，DFS】

第12天树

226. 翻转二叉树【简单，BFS，DFS】

112. 路径总和【简单，栈，递归】

第13天树

700. 二叉搜索树中的搜索【简单】

701. 二叉搜索树中的插入操作【中等】

第14天

98. 验证二叉搜索树【中等】

653. 两数之和 IV - 输入 BST【简单，哈希表】

235. 二叉搜索树的最近公共祖先【简单】

热门文章

最新文章

相关课程

相关电子书

《LeetCode》数据结构入门板块（下）

第7天 链表

141. 环形链表【简单，哈希表，双指针】

21. 合并两个有序链表【简单，迭代，递归】

203. 移除链表元素【简单，迭代，递归】

第8天 链表

206. 反转链表【简单，双指针，栈】

83. 删除排序链表中的重复元素【简单】

第9天 栈/队列

20. 有效的括号【简单，栈】

232. 用栈实现队列【简单，栈】

第10天 树

144. 二叉树的前序遍历【简单】

94. 二叉树的中序遍历【简单】

145. 二叉树的后序遍历【简单】

第11天 树

102. 二叉树的层序遍历【中等，BFS】

104. 二叉树的最大深度【简单，DFS，BFS】

101. 对称二叉树【简单，BFS，DFS】

第12天 树

226. 翻转二叉树【简单，BFS，DFS】

112. 路径总和【简单，栈，递归】

第13天 树

700. 二叉搜索树中的搜索【简单】

701. 二叉搜索树中的插入操作【中等】

第14天

98. 验证二叉搜索树【中等】

653. 两数之和 IV - 输入 BST【简单，哈希表】

235. 二叉搜索树的最近公共祖先【简单】

热门文章

最新文章

相关课程

相关电子书

第7天链表

第8天链表

第9天栈/队列

第10天树

第11天树

第12天树

第13天树