面试常会问到的基础链表和二叉树题目总结

Posted on | Post modified: | In | Views

记录一下几道常见的leetcode题目的解法，都是比较基础的题目。

leetcode-21：合并两个有序链表

题目说明：将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

解题思路：迭代

可以同时遍历两个链表，对比他们的当前节点值，将较小的节点拼接到新的链表，当较短的链表遍历完成，则结束遍历，将长链表剩余的部分拼接到新的链表。

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
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        # 定义头节点、头指针
        cur = head = ListNode()
        
        # 循环遍历两个链表，如短链表遍历结束则结束循环
        while l1 and l2:
            # 值小的节点拼在头节点后，并向后移动节点
            if l1.val <= l2.val:
                cur.next = l1
                l1 = l1.next
            else:
                cur.next = l2
                l2 = l2.next
                
            # 向后移动头指针
            cur = cur.next
        
        # 将长链表拼接
        cur.next = l1 if l1 else l2
        
        return head.next

时间复杂度：O(n+m)，n、m分别为两个链表的长度，因为遍历的总长度为两个链表的长度之和。

空间复杂度：O(1)，只需要常数的空间存放若干变量。

leetcode-94：二叉树的中序遍历

题目说明：给定一个二叉树的根节点 root ，返回它的 中序 遍历。

解题思路一：递归

递归打印二叉树中序遍历的节点值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        
        def inOrder(root, res):
            if not root: return 
            inOrder(root.left, res)
            res.append(root.val)
            inOrder(root.right, res)
        
        res = []
        inOrder(root, res)

        return res

时间复杂度：O(n)，n为二叉树节点个数，每个节点都会被访问一次。

空间复杂度：O(n)，取决于栈深度，当二叉树为链式结构时，栈的深度为n。

解题思路二：迭代

用栈来实现递归中使用到的栈。

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.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        # 定义栈模拟中序遍历
        stack = []
        # 节点值列表
        res = []
        # 遍历树节点
        while root or stack:
            while root:
                # 当前节点存在则入栈
                stack.append(root)
                root = root.left
            # 当前节点为空时出栈
            root = stack.pop(-1)
            res.append(root.val)
            root = root.right
        return res

时间复杂度：O(n)，n为二叉树节点个数，每个节点都会被访问一次。

空间复杂度：O(n)，取决于栈深度，当二叉树为链式结构时，栈的深度为n。

leetcode-104：二叉树的最大深度

题目说明：给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

解题思路：递归

1
2
3
4
5
6
7
8
9
10
11
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if not root:
            return 0
        return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1

时间复杂度：O(n)，n为节点个数，二叉树每个节点都会被遍历一次。

空间复杂度：O(h)，h为二叉树的高度，空间复杂度取决于二叉树的高度

leetcode-206：反转链表

题目说明：给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

解题思路一：迭代

运用Python解包赋值的方式，pre指向当前节点cur，pre.next指向前节点pre（注意，此时pre.next的pre已被赋值为cur，而后面的pre还是None），当前节点cur指向下一个节点cur.next

1
2
3
4
5
6
7
8
9
10
11
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:    
    def reverseList(self, head: ListNode) -> ListNode:
        pre, cur = None, head
        while cur:
            pre, pre.next, cur = cur, pre, cur.next
        return pre

时间复杂度：O(n)，n为链表长度，每个链表都会被遍历一次。

空间复杂度：O(1)。

解题思路二：迭代

反转时，要先保存当前节点的下一个节点，防止其丢失。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        pre, cur = None, head
        while cur:
            next = cur.next
            cur.next = pre
            pre = cur
            cur = next
        return pre

时间复杂度：O(n)。

空间复杂度：O(1)。

解题思路三：递归

递归可理解为先将链表递归到最后一个节点的前一个节点，结束递归时修改这个节点的指针进行操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        # 递归终止条件：空链表或者当前节点为尾节点，则返回，该尾节点为新链表的头节点
        if not head or not head.next:
            return head
        
        new_head = self.reverseList(head.next)
        # 对每个递归的节点执行以下操作：将当前节点的下一个节点的后指针指向当前节点，然后将当前节点的下一个节点置空
        head.next.next = head
        head.next = None
        
        # 最后返回新链表
        return new_head

时间复杂度：O(n)。

空间复杂度：O(n），n为链表长度，递归深度最多为n层。

leetcode-226：翻转一颗二叉树

解题思路一：广度优先搜索

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.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def invertTree(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        if not root:
            return None
        queue = [root]
        while queue:
            tmp = queue.pop(0)
            tmp.left, tmp.right = tmp.right, tmp.left
            if tmp.left:
                queue.append(tmp.left)
            if tmp.right:
                queue.append(tmp.right)
        return root

时间复杂度：O(n)，n为二叉树节点个数，因为每个节点都会入队出队一次。

空间复杂度：O(n)，n为二叉树节点个数，最快情况为完全二叉树，每个叶子节点都会进队，二叉树叶子节点个数为n/2个，故空间复杂度为O(n)。

解题思路二：深度优先搜索

递归交换当前节点的左右子树，当前节点为空时结束递归。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def invertTree(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        if not root:
            return root
        root.left, root.right = self.invertTree(root.right), self.invertTree(root.left)
        return root

时间复杂度：O(n)，每个节点在递归时都会访问一次。

空间复杂度：O(n)，最坏情况是树成为链式结构，递归的深度为n。

leetcode-617：合并二叉树

题目说明：

给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。 你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。

解题思路：递归

有三种情况：

  • 只有一个树的节点为空，重叠时返回另一个树结点
  • 都为空则返回空
  • 都不为空，创建新的树节点，合并两个树节点的值作为新节点的值，并递归的合并左右子树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def mergeTrees(self, root1: TreeNode, root2: TreeNode) -> TreeNode:
        if not root1:
            return root2
        
        if not root2:
            return root1
        
        merged = TreeNode(root1.val+root2.val)
        
        merged.left = self.mergeTrees(root1.left, root2.left)
        merged.right = self.mergeTrees(root1.right, root2.right)
        
        return merged

时间复杂度：O(min(n, m))，仅在两棵二叉树节点都不为空时才做合并处理，故被访问到的节点数不超过较小的二叉树节点数。

空间复杂度：O(min(n, m))，栈的深度为二叉树高度，递归的层数不会超过较小的二叉树的高度，最坏情况下树为链式结构，高度等于节点数。

leetcode-897：递增顺序搜索树

题目说明：给你一棵二叉搜索树，请你 按中序遍历 将其重新排列为一棵递增顺序搜索树，使树中最左边的节点成为树的根节点，并且每个节点没有左子节点，只有一个右子节点。

解题思路：中序遍历后生成新树

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
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def increasingBST(self, root: TreeNode) -> TreeNode:
        # 定义一个中序遍历函数，将树节点保存到列表中
        def inOrder(root: TreeNode, res: list):
            if not root: return root
            inOrder(root.left, res)
            res.append(root.val)
            inOrder(root.right, res)
        
        res = []
        inOrder(root, res)

        cur = dummy = TreeNode(-1)

        # 列表生成只有右节点的二叉树
        for val in res:
            cur.right = TreeNode(val)
            cur = cur.right
        
        return dummy.right

时间复杂度：O(n)，n为二叉树节点数，每个节点都会遍历两次，故为O(n)。

空间复杂度：O(n)，n为二叉树节点数，需要长度为n的列表保存所有节点的值。

leetcode-938：二叉搜索树的范围和

题目说明：给定二叉搜索树的根结点 root，返回值位于范围 [low, high] 之间的所有结点的值的和。

解题思路一：深度优先搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def rangeSumBST(self, root: TreeNode, low: int, high: int) -> int:
        # 空节点返回0
        if not root:
            return 0

        if root.val < low:
            return self.rangeSumBST(root.right, low, high)
        
        elif root.val > high:
            return self.rangeSumBST(root.left, low, high)
        # 返回当前节点的值并且遍历左右子树
        else:
            return root.val + self.rangeSumBST(root.left, low, high) + self.rangeSumBST(root.right, low, high)

时间复杂度：O(n)

空间复杂度：O(n)

解题思路二：广度优先搜索

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
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def rangeSumBST(self, root: TreeNode, low: int, high: int) -> int:
        # 把当前节点加入队列
        queue = [root]
        sum = 0
        # 遍历队列
        while len(queue):
            # 弹出队列中第一个节点
            root = queue.pop(0)
            # 逐层把该节点的左节点或右节点加入队列
            if root.left:
                queue.append(root.left)
            
            if root.right:
                queue.append(root.right)
            
            if low <= root.val <= high:
                sum += root.val
        
        return sum

时间复杂度：O(n)

空间复杂度：O(n)

解题思路三：前序遍历求和

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.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def rangeSumBST(self, root: TreeNode, low: int, high: int) -> int:
        def preOrder(root, l):
            if not root:
                return
            l.append(root.val)
            preOrder(root.left, l)
            preOrder(root.right, l)
        l = []
        # 前序遍历将链表值存入list
        preOrder(root, l)
        sum = 0
        # 遍历list求和
        for i in l:
            if low <= i <= high:
                sum += i
        return sum

时间复杂度：O(n)

空间复杂度：O(n)