一：环形链表

image-20251002155823727

1. 哈希表

遍历节点并将节点存入哈希表，判断表中是否存在之前的节点即可

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    bool hasCycle(ListNode *head) {
        unordered_set<ListNode*> hashTable;
        while (head != nullptr)
        {
            if (hashTable.count(head)) return true;
            hashTable.insert(head);
            head = head->next;
        }
        return false;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
public class Solution {
    public boolean hasCycle(ListNode head) {
        Set<ListNode> hashTable = new HashSet<ListNode>();
        while (head != null)
        {
            if (hashTable.contains(head)) return true;			// 或if (!hashTable.add(head)) return true;
            hashTable.add(head);
            head = head.next;
        }
        return false;
    }
}
1
2
3
4
5
6
7
8
9
class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        hashTable = set()
        while head:
            if head in hashTable:
                return True
            hashTable.add(head)
            head = head.next
        return False

image-20251002160702258

2. 快慢指针

通过两个不同的指针来表示行进速度，差值为1，从初始到最后相遇相当于快指针多走了一个环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    bool hasCycle(ListNode *head) {
        if (head == nullptr || head->next == nullptr) return false;
        ListNode* fastNode = head->next;        // 相差一个起始位置，从而进入循环
        ListNode* slowNode = head;
        while (slowNode != fastNode)
        {
            if (fastNode == nullptr || fastNode->next == nullptr) return false;
            slowNode = slowNode->next;
            fastNode = fastNode->next->next;
        }
        return true;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) return false;
        ListNode fastNode = head.next;        // 相差一个起始位置，从而进入循环
        ListNode slowNode = head;
        while (slowNode != fastNode)
        {
            if (fastNode == null || fastNode.next == null) return false;
            slowNode = slowNode.next;
            fastNode = fastNode.next.next;
        }
        return true;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        if head is None or head.next is None:
            return False
        fastNode = head.next;        # 相差一个起始位置，从而进入循环
        slowNode = head
        while slowNode != fastNode:
            if fastNode is None or fastNode.next is None:
                return false
            slowNode = slowNode.next
            fastNode = fastNode.next.next
        return True

image-20251002164356176

二：合并两个有序链表

image-20251002165418114

1. 迭代

依次比较两个链表中的值，较小值放在较大值的前面

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
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode* preNode = new ListNode(0);			// 哨兵节点 
        ListNode* cur = preNode;
        if (!list1) return list2;
        if (!list2) return list1;
        while (list1 != nullptr && list2 != nullptr)
        {
            if (list1->val < list2->val)
            {
                cur->next = list1;
                list1 = list1->next;
            } 
            else
            {
                cur->next = list2;
                list2 = list2->next;
            }
            cur = cur->next;
        }
        cur->next = list1 == nullptr ? list2 : list1;
        return preNode->next;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode preNode = new ListNode(0);
        ListNode cur = preNode;
        if (list1 == null) return list2;
        if (list2 == null) return list1;
        while (list1 != null && list2 != null)
        {
            if (list1.val < list2.val)
            {
                cur.next = list1;
                list1 = list1.next;
            } 
            else
            {
                cur.next = list2;
                list2 = list2.next;
            }
            cur = cur.next;
        }
        cur.next = list1 == null ? list2 : list1;
        return preNode.next;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        preNode = ListNode(0)			# 没有new
        cur = preNode
        if not list1:			# 这个判断好像不需要，后面的代码实现同样的功能
            return list2
        if not list2:
            return list1
        while list1 and list2:   
            if list1.val < list2.val:
                cur.next = list1
                list1 = list1.next
            else:
                cur.next = list2
                list2 = list2.next
            cur = cur.next
        if list1:
            cur.next = list1
        else:
            cur.next = list2
        return preNode.next

image-20251002165511762

2. 递归

根据最小值按照相反方向逐一返回

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if (!list1) return list2;
        if (!list2) return list1;
        if (list1->val < list2->val)
        {
            list1->next = mergeTwoLists(list1->next, list2);
            return list1;
        } else
        {
            list2->next = mergeTwoLists(list2->next, list1);
            return list2;
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null) return list2;
        if (list2 == null) return list1;
        if (list1.val < list2.val)
        {
            list1.next = mergeTwoLists(list1.next, list2);
            return list1;
        } else
        {
            list2.next = mergeTwoLists(list2.next, list1);
            return list2;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        if list1 == None:
            return list2
        if list2 == None:
            return list1
        if list1.val < list2.val:
            list1.next = self.mergeTwoLists(list1.next, list2)
            return list1
        else:
            list2.next = self.mergeTwoLists(list2.next, list1)
            return list2

image-20251002173322758

三：二叉树的中序遍历

image-20251008155716618

1. 递归

先逐层访问左节点，然后保存当前值，再访问右节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
private:
    vector<int> nodes;
public:
    vector<int> inorderTraversal(TreeNode* root) {
        recursion(root);
        return nodes;
    }
    void recursion(TreeNode* root)
    {
        if (!root) return;
        recursion(root->left);
        nodes.emplace_back(root->val);
        recursion(root->right);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    private List<Integer> nodes = new ArrayList<Integer>();		// 需要new
    public List<Integer> inorderTraversal(TreeNode root) {
        recursion(root);
        return nodes;
    }
    public void recursion(TreeNode root)
    {
        if (root == null) return;
        recursion(root.left);
        nodes.add(root.val);
        recursion(root.right);
    }
}
1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        self.nodes = []
        self._recursion(root)
        return self.nodes
    def _recursion(self, root: Optional[TreeNode]):
        if not root:
            return
        self._recursion(root.left)
        self.nodes.append(root.val)				# 这里使用append
        self._recursion(root.right)

image-20251002211520678

2. 迭代

这里需要一个栈来维护树的层次

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
private:
    vector<int> nodes;
public:
    vector<int> inorderTraversal(TreeNode* root) {
        stack<TreeNode*> treeStack;
        while (root != nullptr || !treeStack.empty())       // 需要保证栈中的内容处理完毕
        {
            while (root != nullptr)
            {
                treeStack.push(root);           // 入栈
                root = root->left;
            }
            root = treeStack.top();             // 栈顶
            nodes.emplace_back(root->val);
            treeStack.pop();                    // 拿到数据出栈
            root = root->right;
       } 
       return nodes;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> nodes = new ArrayList<Integer>();
        Deque<TreeNode> treeDeque = new ArrayDeque<TreeNode>();
        while (root != null || !treeDeque.isEmpty())        // 使用isEmpty
        {
            while (root != null)
            {
                treeDeque.push(root);
                root = root.left;
            }
            root = treeDeque.pop();
            nodes.add(root.val);
            root = root.right;
        }
        return nodes;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        nodes = []
        treeStack = []
        while root is not None or treeStack:
            while root is not None:
                treeStack.append(root)
                root = root.left
            root = treeStack.pop()
            nodes.append(root.val)
            root = root.right
        return nodes

image-20251002213028881

3. Morris 中序遍历

查找第一个左节点，然后遍历该结点的右节点，将最后一个右节点指向根节点，依次循环，访问时向右遍历即可

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
class Solution {
private:
    vector<int> nodes;
public:
    vector<int> inorderTraversal(TreeNode* root) {
        TreeNode* cur = nullptr;
        while (root)
        {
            if (root->left)
            {
                cur = root->left;
                while (cur->right != nullptr && cur->right != root )
                {
                    cur = cur->right;
                }
                if (cur->right == nullptr)
                {
                    cur->right = root;
                    root = root->left;
                } else
                {
                    nodes.emplace_back(root->val);
                    cur->right = nullptr;           // 要赋空，否则死循环
                    root = root->right;
                }
            } else 
            {
                nodes.emplace_back(root->val);
                root = root->right;
            }
        }
        return nodes;
    }
};
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
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> nodes = new ArrayList<Integer>();
        TreeNode cur = null;
        while (root != null)
        {
            if (root.left != null)
            {
                cur = root.left;
                while (cur.right != null && cur.right != root)     // cur.right != root必须有
                {
                    cur = cur.right;
                }
                if (cur.right == null)
                {
                    cur.right = root;
                    root = root.left;
                } else
                {
                    nodes.add(root.val);
                    cur.right = null;           // 要赋空，否则死循环
                    root = root.right;
                }
            } else 
            {
                nodes.add(root.val);
                root = root.right;
            }
        }
        return nodes;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        nodes = []
        cur = None
        while root is not None:
            if root.left is not None:
                cur = root.left
                while cur.right is not None and cur.right is not root:     # cur.right is not root必须有
                    cur = cur.right
                if cur.right == None:
                    cur.right = root
                    root = root.left
                else:
                    nodes.append(root.val)
                    cur.right = None           # 要赋空，否则死循环
                    root = root.right
            else:
                nodes.append(root.val)
                root = root.right  
        return nodes

image-20251002221448936

四：二叉树的最大深度

image-20251002224629513

1. 深度优先搜索

利用递归依次遍历左右节点，取其中的较大值

1
2
3
4
5
6
7
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
class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1; // 使用Math.max
    }
}
1
2
3
4
5
class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if root == None:
            return 0
        return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1		# 加self

image-20251002224736035

2. 广度优先搜索

用队列维护

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (root == nullptr) return 0;
        queue<TreeNode*> treeQueue;
        treeQueue.push(root);
        int depth = 0;
        while (!treeQueue.empty())
        {
            int size = treeQueue.size();
            while (size > 00)
            {
                TreeNode* root = treeQueue.front();
                treeQueue.pop();
                if (root->left) treeQueue.push(root->left);
                if (root->right) treeQueue.push(root->right);
                --size;
            }
            ++depth;
        }
        return depth
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        Queue<TreeNode> treeQueue = new LinkedList<TreeNode>();
        treeQueue.offer(root);      // 使用offer
        int depth = 0;
        while (treeQueue.isEmpty() == false)
        {
            int size = treeQueue.size();
            while (size > 0)
            {
                TreeNode newroot = treeQueue.poll();       // 使用poll
                if (newroot.left != null) treeQueue.offer(newroot.left);
                if (newroot.right != null) treeQueue.offer(newroot.right);
                --size;
            }
            ++depth;
        }
        return depth;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if root == None:
            return 0
        treeQueue = deque([root])         # 使用deque    
        depth = 0
        while treeQueue:
            size = len(treeQueue)
            while size > 0:
                newroot = treeQueue.popleft()       # 使用popleft
                if newroot.left:
                    treeQueue.append(newroot.left)      # 使用append
                if newroot.right:
                    treeQueue.append(newroot.right)
                size -= 1
            depth += 1
        return depth

image-20251002224748499

五：翻转二叉树

image-20251002233152395

1. 递归

左右节点依次递归，找到叶子节点，然后交换左右位置

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (root == nullptr) return nullptr;
        TreeNode* temp = root->left;
        root->left = invertTree(root->right);
        root->right = invertTree(temp);
        return root;
    }
};
1
2
3
4
5
6
7
8
9
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return null;
        TreeNode temp = root.left;
        root.left = invertTree(root.right);
        root.right = invertTree(temp);
        return root;
    }
}
1
2
3
4
5
6
7
8
class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if root == None:
            return None
        temp = root.left		# 或平行赋值
        root.left = self.invertTree(root.right)
        root.right = self.invertTree(temp)
        return root

image-20251002234846128

2. 迭代

用队列维护

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (root == nullptr) return nullptr;
        stack<TreeNode*> treeStack;
        TreeNode* cur = nullptr;
        TreeNode* temp = nullptr;
        treeStack.push(root);
        while (!treeStack.empty())
        {
            cur = treeStack.top();
            treeStack.pop();
            if (cur->left != nullptr) treeStack.push(cur->left);
            if (cur->right != nullptr) treeStack.push(cur->right);
            temp = cur->left;
            cur->left = cur->right;
            cur->right = temp;
        }
        return root;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return null;
        Stack<TreeNode> treeStack = new Stack<>();
        treeStack.add(root);
        TreeNode cur = null;
        TreeNode temp = null;
        while (!treeStack.isEmpty())
        {
            cur = treeStack.pop();
            if (cur.left != null) treeStack.add(cur.left);
            if (cur.right != null) treeStack.add(cur.right);
            temp = cur.left;
            cur.left = cur.right;
            cur.right = temp;
        }
        return root;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if root == None:
            return None
        treeStack = []
        treeStack.append(root)
        while treeStack:
            cur = treeStack.pop()
            if cur.left != None: treeStack.append(cur.left)
            if cur.right != None: treeStack.append(cur.right)
            cur.left, cur.right = cur.right, cur.left
        return root

image-20251002234904274