LeetCode题目总结-二叉树

发表于 | 分类于 ， | 评论数： | 阅读次数：
本文字数： 24k | 阅读时长 ≈ 21 分钟

树是一种以层次化方式组织和存放数据的特定数据结构。

树有两个主要特征：

  • 每个项都有多个子节点
  • 除了叫做根的特殊的项，所有其他的项都只有一个父节点

二叉树(binary tree)是一种特殊的树结构，它每个节点最多有两个子结点，亦称左孩子和右孩子。

这里总结了LeetCode中二叉树相关的题目，我把这些题目分成了以下五个部分：

二叉树的存储结构

二叉树的存储结构 TreeNode 为：

1
2
3
4
5
class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

二叉树的性质相关题目

树的性质判断是树的数据结构比较基本的操作。

100-相同的树

题目描述

给定两个二叉树，编写一个函数来检验它们是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

示例 1:

1
2
3
4
5
6
7
输入:       1         1
          / \       / \
         2   3     2   3

        [1,2,3],   [1,2,3]

输出: true

示例 2:

1
2
3
4
5
6
7
输入:      1          1
          /           \
         2             2

        [1,2],     [1,null,2]

输出: false

示例 3:

1
2
3
4
5
6
7
输入:       1         1
          / \       / \
         2   1     1   2

        [1,2,1],   [1,1,2]

输出: false

思路

方法1：递归

终止条件与返回值：

  • 当两棵树的当前节点都为 null 时返回 true
  • 当其中一个为 null 另一个不为 null 时返回 false
  • 当两个都不为空但是值不相等时，返回 false

执行过程：当满足终止条件时进行返回，不满足时分别判断左子树和右子树是否相同，其中要注意代码中的短路效应。

下面是一个图解：

方法2：迭代

首先用一个栈来保存根节点p，q。接着不断遍历这个栈。

  1. 我们从栈中拿出两个元素进行比较，如果这两个元素不等(一个是空一个不为空，或者两个节点的值不等)，就直接返回false。

  2. 如果这两个节点的值相等，就继续把p节点的左孩子,q节点的左孩子放入栈中；再把p节点的右孩子，q节点的右孩子放入栈中。

重复这个步骤，直到栈为空。

如果整个循环遍历完了，说明两个树的元素都是相等的，返回true。

画解算法：100. 相同的树

Python实现

方法1：递归

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        if p == None and q == None:
            return True

        if p == None or q == None:
            return False

        if p.val != q.val:
            return False
        
        return self.isSameTree(p.left,q.left) and self.isSameTree(p.right,q.right)

方法2：迭代

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        stack = []
        stack.append((p,q))

        while stack:
            p,q = stack.pop()
            if p == None and q == None:
                continue
            elif p == None or q == None:
                return False
            elif p.val != q.val:
                return False
            elif p.val == q.val:
                stack.append((p.left,q.left))
                stack.append((p.right,q.right))
        
        return True

101-对称二叉树

题目描述

给定一个二叉树，检查它是否是镜像对称的。

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

1
2
3
4
5
    1
   / \
  2   2
 / \ / \
3  4 4  3

但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

1
2
3
4
5
  1
 / \
2   2
 \   \
 3    3

说明：如果你可以运用递归和迭代两种方法解决这个问题，会很加分。

思路

如果一个树的左子树与右子树镜像对称，那么这个树是对称的。

因此，该问题可以转化为：两个树在什么情况下互为镜像？

如果同时满足下面的条件，两个树互为镜像：

  • 它们的两个根结点具有相同的值。
  • 每个树的右子树都与另一个树的左子树镜像对称。

Python实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        if root == None:
            return True
        
        return self.isMirror(root.left,root.right)
        
        
    def isMirror(self, t1, t2):
        if t1 == None and t2 == None:
            return True

        if t1 == None or t2 == None:
            return False

        if t1 != None and t2 != None:
            if t1.val == t2.val:
                return self.isMirror(t1.left,t2.right) and self.isMirror(t1.right,t2.left)
            else:
                return False

110-平衡二叉树

题目描述

给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1。

示例 1:

1
2
3
4
5
6
7
8
给定二叉树 [3,9,20,null,null,15,7]

    3
   / \
  9  20
    /  \
   15   7
返回 true 。

示例 2:

1
2
3
4
5
6
7
8
9
10
给定二叉树 [1,2,2,3,3,null,null,4,4]

       1
      / \
     2   2
    / \
   3   3
  / \
 4   4
返回 false 。

思路

方法1：自顶向下暴力递归

构造一个获取当前节点最大深度的方法 depth() ，通过比较左右子树最大高度差abs(self.depth(root.left) - self.depth(root.right))，来判断以此节点为根节点下是否是二叉平衡树；

  • 从顶至底DFS，以每个节点为根节点，递归判断是否是平衡二叉树：
    • 若所有根节点都满足平衡二叉树性质，则返回 True ；
    • 若其中任何一个节点作为根节点时，不满足平衡二叉树性质，则返回False。

本方法产生大量重复的节点访问和计算，最差情况下时间复杂度 O(N^2)。

方法2：自底向上（提前阻断）

对二叉树做深度优先遍历DFS，递归过程中：

  • 终止条件：当DFS越过叶子节点时，返回高度0；
  • 返回值：
    • 从底至顶，返回以每个节点root为根节点的子树最大高度（左右子树中最大的高度值加1，即max(left,right) + 1)）
    • 当我们发现有一例 左/右子树高度差 ＞ 1 的情况时，代表此树不是平衡树，返回-1
    • 当发现不是平衡树时，后面的高度计算都没有意义了，因此一路返回-1，避免后续多余计算。

最差情况是对树做一遍完整DFS，时间复杂度为 O(N)。

Python实现

方法1：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def isBalanced(self, root: TreeNode) -> bool:
        if root == None:
            return True

        # 当前节点满足平衡树，继续递归判断子树是否满足平衡树条件
        if abs(self.depth(root.left)-self.depth(root.right)) <= 1:
            return self.isBalanced(root.left) and self.isBalanced(root.right)
        else:
            return False

    # 计算树高度
    def depth(self, root):
        if root == None:
            return 0

        if root.left == None and root.right == None:
            return 1

        if root.left != None or root.right != None:
            return 1+max(self.depth(root.left),self.depth(root.right))

方法2：

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
class Solution:
    def isBalanced(self, root: TreeNode) -> bool:
        if self.depth(root) == -1:
            return False
        else:
            return True

    def depth(self, root):
        if root == None:
            return 0

        depth_left = self.depth(root.left)
        # 提前阻断
        if depth_left == -1:
            return -1

        depth_right = self.depth(root.right)
        # 提前阻断
        if depth_right == -1:
            return -1

        if abs(depth_left-depth_right) <= 1:
            return 1+max(depth_left,depth_right)
        # 提前阻断
        else:
            return -1

104-二叉树的最大深度

题目描述

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明：叶子节点是指没有子节点的节点。

示例：给定二叉树 [3,9,20,null,null,15,7]，

1
2
3
4
5
  3
 / \
9  20
  /  \
 15   7

返回它的最大深度 3 。

思路

方法1：迭代

层次遍历二叉树，如果树为空，直接返回0。否则将树和深度值1入队列，逐一弹出队列中节点：

  • 若某节点左右子树均为空，此节点即为叶子节点，我们将它的深度和最大深度max_depth进行比较，更新最大深度。
  • 若其存在子树，则将其存在的子树和子树深度入队列。

方法2：递归

递归结束条件：

  • 当 root 节点左右孩子都为空（叶子节点）时，返回 1
  • 当 root 节点左右孩子至少有一个不为空时，返回左右孩子较大深度的节点值

Python实现

方法1：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if root == None:
            return 0

        queue = [(root,1)]
        max_depth = 0

        while queue:
            node,depth = queue.pop(0)
            max_depth = max(max_depth,depth)

            if node.left != None:
                queue.append((node.left,depth+1))
            if node.right != None:
                queue.append((node.right,depth+1))

        return max_depth

方法2：

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if root == None:
            return 0

        # 叶子节点，返回1
        if root.left == None and root.right == None:
            return 1

        # 当左右孩子至少有一个不为空时，返回左右孩子较大深度的节点值
        if root.left != None or root.right != None:
            return 1+max(self.maxDepth(root.left),self.maxDepth(root.right))

111-二叉树的最小深度

题目描述

给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明: 叶子节点是指没有子节点的节点。

示例：给定二叉树[3,9,20,null,null,15,7],

1
2
3
4
5
  3
 / \
9  20
  /  \
 15   7

返回它的最小深度2.

思路

方法1：迭代

层次遍历二叉树，如果树为空，直接返回0。否则将树和深度值1入队列，逐一弹出队列中节点：

  • 若某节点左右子树均为空，此节点即为叶子节点，我们将它的深度和最小深度min_depth进行比较，更新最小深度。
  • 若其存在子树，则将其存在的子树和子树深度入队列。

实际上，因为层次遍历是一层一层遍历的，所以第一个叶子节点即为最小深度的叶子节点，直接返回其深度即可。这样就不用遍历所有的节点。

方法2：递归

递归解法的关键是搞清楚递归结束条件：

  • 当 root 节点左右孩子都为空（叶子节点）时，返回 1
  • 当 root 节点左右孩子有一个为空时，返回不为空的孩子节点的深度
  • 当 root 节点左右孩子都不为空时，返回左右孩子较小深度的节点值

Python实现

方法1：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def minDepth(self, root: TreeNode) -> int:
        if root == None:
            return 0
      
        queue = [(root,1)]

        while queue:
            node,depth = queue.pop(0)
            if node.left == None and node.right == None:
                return depth

            if node.left != None:
                queue.append((node.left,depth+1))

            if node.right != None:
                queue.append((node.right,depth+1))

方法2：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def minDepth(self, root: TreeNode) -> int:
        if root == None:
            return 0
        
        # 叶子节点，返回1
        if root.left == None and root.right == None:
            return 1

        # 当左右孩子有一个为空时，返回不为空的孩子节点的深度
        if root.left == None or root.right == None:
            return 1+max(self.minDepth(root.left),self.minDepth(root.right))

        # 当左右孩子都不为空时，返回左右孩子较小深度的节点值
        if root.left != None and root.right != None:
            return 1+min(self.minDepth(root.left),self.minDepth(root.right))

662-二叉树最大宽度

题目描述

给定一个二叉树，编写一个函数来获取这个树的最大宽度。树的宽度是所有层中的最大宽度。这个二叉树与满二叉树（full binary tree）结构相同，但一些节点为空。

每一层的宽度被定义为两个端点（该层最左和最右的非空节点，两端点间的null节点也计入长度）之间的长度。

示例 1:

1
2
3
4
5
6
7
8
9
10
输入: 

           1
         /   \
        3     2
       / \     \  
      5   3     9 

输出: 4
解释: 最大值出现在树的第 3 层，宽度为 4 (5,3,null,9)。

示例 2:

1
2
3
4
5
6
7
8
9
10
输入: 

          1
         /  
        3    
       / \       
      5   3     

输出: 2
解释: 最大值出现在树的第 3 层，宽度为 2 (5,3)。

示例 3:

1
2
3
4
5
6
7
8
9
10
输入: 

          1
         / \
        3   2 
       /        
      5      

输出: 2
解释: 最大值出现在树的第 2 层，宽度为 2 (3,2)。

示例 4:

1
2
3
4
5
6
7
8
9
10
11
输入: 

          1
         / \
        3   2
       /     \  
      5       9 
     /         \
    6           7
输出: 8
解释: 最大值出现在树的第 4 层，宽度为 8 (6,null,null,null,null,null,null,7)。

注意: 答案在32位有符号整数的表示范围内。

思路

因为两端点间的None值也计入，所以这里我们不能简单的统计每一层的节点数，这里我们可以考虑给树中的每一个节点进行编号，根节点为1，然后如果是左节点，值为根节点的二倍；如果是右节点，值为根节点的二倍加一。

这里我用层次遍历，采用一个队列记录每一个节点的节点以及号码，一层的首末元素的编号差就是该层的最大宽度。

Python实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def widthOfBinaryTree(self, root: TreeNode) -> int:
        queue = [(root,1)]
        width = 0
        while queue:
            length = len(queue)
            for i in range(length):
                node,nums = queue.pop(0)
                # 记录该层第一个节点的编号、最后一个节点的编号
                if i == 0:
                    first_num = nums
                if i == length-1:
                    last_num = nums
                    # 更新最大宽度
                    width = max(width,last_num-first_num+1)
                # 左右子树入队
                if node.left != None:
                    queue.append((node.left,2*nums))
                if node.right != None:
                    queue.append((node.right,2*nums+1))
        
        return width

二叉树的遍历相关题目

遍历的含义就是把树的所有节点（Node）按照某种顺序访问一遍。包括前序，中序，后序，层序4种遍历方法。

  1. 以图的深度优先搜索为原型的遍历

在这种类型中，递归的实现方式是非常简单的，只需要递归左右结点，直到结点为空作为结束条件就可以，哪种序就取决于你访问结点的时间。

不过一般这不能满足面试官的要求，可能会接着问能不能用非递归实现一下，这个说起来比较简单，其实就是用一个栈手动模拟递归的过程。

有时候非递归还是不能满足面试官，还会问一问，上面的做法时间和空间复杂度是多少。我们知道，正常遍历时间复杂度是O(n)，而空间复杂度是则是递归栈（或者自己维护的栈）的大小，也就是O(logn)。他会问能不能够在常量空间内解决树的遍历问题呢？确实还真可以，这里就要介绍一下Morris遍历。

Morris遍历方法用了线索二叉树，这个方法不需要为每个节点额外分配指针指向其前驱和后继结点，而是利用叶子节点中的右空指针指向中序遍历下的后继节点就可以了。这样就节省了需要用栈来记录前驱或者后继结点的额外空间，所以可以达到O(1)的空间复杂度。不过这种方法有一个问题就是会暂时性的改动树的结构，这在程序设计中并不是很好的习惯，这些在面试中都可以和面试官讨论，一般来说问到这里不会需要进行Morris遍历方法的代码实现了，只需要知道这种方法和他的主要优劣势就可以了。

  1. 以图的广度优先搜索为原型的遍历，在树中称为层序遍历，LeetCode中有三种：自顶向下层序、自底向上层序、锯齿层序遍历。

自顶向下层序遍历其实比较简单，代码基本就是图的广度优先搜索，思路就是维护一个队列存储上一层的结点，逐层访问。而自底向上层序层序遍历则要从最后一层倒序访问上来，这个我没有想到太好的方法，现在的实现就是把自顶向下层序遍历得到的层放入数据结构然后reverse过来。至于锯齿层序遍历因为每一层访问顺序有所改变，而且是每次都反转顺序，这让我们想到栈这个数据结构，所以这里不用队列而改用栈来保存，就可以满足每层反转访问顺序的要求了。

层次遍历相关的题目：

详细题解

路径和相关题目

树的求和属于树的题目中比较常见的，因为可以有几种变体，灵活度比较高，也可以考察到对于树的数据结构和递归的理解。

112-路径总和

题目描述

给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。

说明: 叶子节点是指没有子节点的节点。

示例:
给定如下二叉树，以及目标和 sum = 22，

1
2
3
4
5
6
7
      5
     / \
    4   8
   /   / \
  11  13  4
 /  \      \
7    2      1

返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。

思路

这道题是判断是否存在从根到叶子的路径和跟给定sum相同。树的题目基本都是用递归来解决，主要考虑两个问题：

  1. 如何把问题分治成子问题给左子树和右子树。这里就是看看左子树和右子树有没有存在和等于sum减去当前结点值的路径，只要有一个存在，那么当前结点就存在路径。
  2. 考虑结束条件是什么：
    • 结束条件1：如果当前节点是空的，则返回false。
    • 结束条件2：如果是叶子，那么如果剩余的sum等于当前叶子的值，则找到满足条件的路径，返回true。

想清楚上面两个问题，那么实现起来就是一次树的遍历，按照刚才的分析用参数或者返回值传递需要维护的值，然后按照递归条件和结束条件进行返回即可。算法的时间复杂度是一次遍历O(n)，空间复杂度是栈的大小O(logn)。

Python实现——递归

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def hasPathSum(self, root: TreeNode, sum: int) -> bool:
        if root == None:
            return False

        # 当前节点是叶子，检查 root.val 值是否为 sum
        if root.left == None and root.right == None and root.val == sum:
            return True

        # 当前节点不是叶子，对它的所有孩子节点，递归调用 hasPathSum() 函数
        return self.hasPathSum(root.left,sum-root.val) or self.hasPathSum(root.right,sum-root.val)
  • 时间复杂度：我们访问每个节点一次，时间复杂度为 O(N) ，其中 N 是节点个数。
  • 空间复杂度：最坏情况下，整棵树是非平衡的，例如每个节点都只有一个孩子，递归会调用 N 次（树的高度），因此栈的空间开销是 O(N)。但在最好情况下，树是完全平衡的，高度只有 log(N)，因此在这种情况下空间复杂度只有 O(log(N)) 。

Python实现——迭代

我们可以用栈将递归转成迭代的形式。

栈中保存当前节点前的剩余值就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def hasPathSum(self, root: TreeNode, sum: int) -> bool:
        if root == None:
            return False

        stack = [(root,sum)]
        while stack:
            node,sum = stack.pop()
            # 判断叶子节点是否满足了条件
            if node.left == None and node.right == None and node.val == sum:
                return True
            
            # 左节点不为空，我们把左节点和剩余值打包压栈
            if node.left != None:
                stack.append((node.left,sum-node.val))
            # 右节点不为空，我们把右节点和剩余值打包压栈
            if node.right != None:
                stack.append((node.right,sum-node.val))

        return False

113-路径总和ii

题目描述

给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。

说明: 叶子节点是指没有子节点的节点。

示例:
给定如下二叉树，以及目标和 sum = 22，

1
2
3
4
5
6
7
      5
     / \
    4   8
   /   / \
  11  13  4
 /  \    / \
7    2  5   1

返回:

1
2
3
4
[
   [5,4,11,2],
   [5,8,4,5]
]

思路

这道题思路和112-路径总和是完全一样的，只是需要输出所有路径，所以需要数据结构来维护路径，添加两个参数，一个用来维护走到当前结点的路径，一个用来保存满足条件的所有路径，思路上递归条件和结束条件是完全一致的，空间上这里会依赖于结果的数量了。

Python实现——递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]:
        # 辅助函数（因为需要一个变量记录路径）       
        def helper(root, sum, temp):
            if root == None:
                return

            # 路径和满足sum，路径添加到结果数组res
            if root.left == None and root.right == None and root.val == sum:
                temp += [root.val]
                res.append(temp)

            # 递归搜索左右子树，传入剩余和以及路径
            helper(root.left,sum-root.val,temp+[root.val])
            helper(root.right,sum-root.val,temp+[root.val])


        res = []
        helper(root,sum,[])

        return res

Python实现——迭代

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:
    def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]:
        if root == None:
            return []

        res = []
        temp = []
        stack = [(root,sum,temp)]

        while stack:
            node,sum,temp = stack.pop()
            # 判断叶子节点是否满足了条件
            if node.left == None and node.right == None and node.val == sum:
                temp += [node.val]
                res.append(temp)

            if node.left != None:
                stack.append((node.left,sum-node.val,temp + [node.val]))

            if node.right != None:
                stack.append((node.right,sum-node.val,temp + [node.val]))

        return res

129-求根到叶子节点数字之和

题目描述

给定一个二叉树，它的每个结点都存放一个 0-9 的数字，每条从根到叶子节点的路径都代表一个数字。

例如，从根到叶子节点路径 1->2->3 代表数字 123。

计算从根到叶子节点生成的所有数字之和。

说明: 叶子节点是指没有子节点的节点。

示例 1:

1
2
3
4
5
6
7
8
9
输入: [1,2,3]
    1
   / \
  2   3
输出: 25
解释:
从根到叶子节点路径 1->2 代表数字 12.
从根到叶子节点路径 1->3 代表数字 13.
因此，数字总和 = 12 + 13 = 25.

示例 2:

1
2
3
4
5
6
7
8
9
10
11
12
输入: [4,9,0,5,1]
    4
   / \
  9   0
 / \
5   1
输出: 1026
解释:
从根到叶子节点路径 4->9->5 代表数字 495.
从根到叶子节点路径 4->9->1 代表数字 491.
从根到叶子节点路径 4->0 代表数字 40.
因此，数字总和 = 495 + 491 + 40 = 1026.

思路

这道题目相比112-路径总和，增加了两个变化：

  1. 每一个结点相当于位上的值。我们只需要每一层乘以10加上自己的值就可以了。
  2. 所有路径需要累加起来。我们只需要在最后对结果列表进行求和即可。

Python实现——递归

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:
    def sumNumbers(self, root: TreeNode) -> int:
        def helper(root, nums):
            if root == None:
                return 0

            # 更新路径和
            nums *= 10
            nums += root.val

            # 如果已经是叶子节点，保存路径和到列表中
            if root.left == None and root.right == None:
                res.append(nums)

            if root.left != None:
                helper(root.left,nums)

            if root.right != None:
                helper(root.right,nums)

        
        res = []
        helper(root,0)

        return sum(res)

Python实现——迭代

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:
    def sumNumbers(self, root: TreeNode) -> int:
        if root == None:
            return 0

        stack = [(root,0)]
        res = []

        while stack:
            node,nums = stack.pop()
            # 更新路径和
            nums *= 10
            nums += node.val

            # 如果已经是叶子节点，保存路径和到列表中
            if node.left == None and node.right == None:
                res.append(nums)

            if node.left != None:
                stack.append((node.left,nums))

            if node.right != None:
                stack.append((node.right,nums))

        return sum(res)

257-二叉树的所有路径

题目描述

给定一个二叉树，返回所有从根节点到叶子节点的路径。

说明: 叶子节点是指没有子节点的节点。

示例:

1
2
3
4
5
6
7
8
9
10
11
输入:

   1
 /   \
2     3
 \
  5

输出: ["1->2->5", "1->3"]

解释: 所有根节点到叶子节点的路径为: 1->2->5, 1->3

思路

我们维护一个队列，存储节点以及根到该节点的路径。一开始这个队列里只有根节点。在每一步迭代中，我们取出队列中的首节点，如果它是一个叶子节点，则将它对应的路径加入到答案中。如果它不是一个叶子节点，则将它的所有孩子节点加入到队列的末尾。当队列为空时，迭代结束。

Python实现

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
class Solution:
    def binaryTreePaths(self, root: TreeNode) -> List[str]:
        if root == None:
            return None

        res = []
        queue = [(root,'')]

        while queue:
            temp = ''
            length = len(queue)

            for _ in range(length):
                node,temp = queue.pop(0)
                temp += str(node.val)

                # 如果是叶子节点，记录路径
                if node.left == None and node.right == None:    
                    res.append(temp)

                # 格式要求
                temp += '->'

                if node.left != None:
                    queue.append((node.left,temp))

                if node.right != None:
                    queue.append((node.right,temp))

        return res

二叉树的构建相关题目

这类题目本质还是用递归的手法来实现，但是这类题目有一个特点，就是它是构建一棵树，而不是给定一棵树，然后进行遍历，所以实现起来思路上有点逆向。

思路就是在递归中创建根节点，然后找到将元素劈成左右子树的方法，递归得到左右根节点，接上创建的根然后返回。方法还是比较具有模板型的。

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

题目描述

根据一棵树的前序遍历与中序遍历构造二叉树。

注意:你可以假设树中没有重复的元素。

例如，给出

  • 前序遍历 preorder = [3,9,20,15,7]
  • 中序遍历 inorder = [9,3,15,20,7]

返回如下的二叉树：

1
2
3
4
5
  3
 / \
9  20
  /  \
 15   7

思路

前序遍历数组的第1个数（索引为0）的数一定是二叉树的根结点，于是可以在中序遍历中找这个根结点的索引，然后把“前序遍历数组”和“中序遍历数组”分为两个部分，就分别对应二叉树的左子树和右子树，分别递归完成就可以了。

下面是一个具体的例子，演示了如何计算数组子区间的边界：

Python实现——递归

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        if len(preorder) == 0:
            return None
        
        root = TreeNode(preorder[0])
        mid = inorder.index(preorder[0])

        # 递归构造左子树、右子树
        root.left = self.buildTree(preorder[1:mid+1],inorder[0:mid])
        root.right = self.buildTree(preorder[mid+1:],inorder[mid+1:])
        return root
  • 时间复杂度：O(N^2)，这里 N 是二叉树的结点个数，每调用一次递归方法创建一个结点，一共创建 N 个结点，在中序遍历中找到根结点在中序遍历中的位置，是与 N 相关的，这里不计算递归方法占用的时间。
  • 空间复杂度：O(1)，这里不计算递归方法占用的空间。

Python实现——哈希表优化

我们可以用哈希表（字典）来存储中序遍历，这样就可以在O(1)时间复杂度下找到根结点在中序遍历数组中的索引。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        if len(preorder) == 0:
            return None
        
        root = TreeNode(preorder[0])
        
        # 哈希表存储中序遍历的值、索引
        dicts = {var:i for i,var in enumerate(inorder)}
        index = dicts[preorder[0]]

        # 递归构造左子树、右子树
        root.left = self.buildTree(preorder[1:index+1],inorder[:index])
        root.right = self.buildTree(preorder[index+1:],inorder[index+1:])

        return root

上面的代码在递归函数里面建立哈希表，这会导致哈希表一共建立二叉树节点个数次（即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
class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        # 辅助函数
        def helper(pre_left,pre_right,in_left,in_right):
            if pre_left == pre_right:
                return None

            # 构建当前“根”
            root = TreeNode(preorder[pre_left])
            # 从哈希表中找到当前“根”的索引
            index = dicts[preorder[pre_left]]

            # 更新前序遍历、中序遍历边界，然后递归构建左右子树
            # 我们可以通过“前序和中序个数是相同”这个隐含条件，求出前序左右边界
            root.left = helper(pre_left+1,pre_left+1+index-in_left,in_left,index)
            # 根据上面用过的，写出剩下的
            root.right = helper(pre_left+1+index-in_left,pre_right,index+1,in_right)
            
            return root
        
        # 哈希表存储中序遍历的值、索引
        dicts = {var:i for i,var in enumerate(inorder)}

        # 调用辅助函数
        root = helper(0,len(preorder),0,len(inorder))
        return root

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

题目描述

根据一棵树的中序遍历与后序遍历构造二叉树。

注意：你可以假设树中没有重复的元素。

例如，给出

1
2
中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]

返回如下的二叉树：

1
2
3
4
5
  3
 / \
9  20
  /  \
 15   7

思路

这道题目类似105题。

下面是一个图解：

分治法（Python、Java）

Python实现——递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
        if len(postorder) == 0:
            return None

        # 后序遍历的最后一个结点就是根结点
        root = TreeNode(postorder[-1])
        # 在中序遍历中找到根结点的索引，得到左右子树的一个划分
        mid = inorder.index(postorder[-1])

        # 这里的列表切片使用的是复制值，使用了一些空间，因此空间复杂度是 O(N)
        root.left = self.buildTree(inorder[:mid],postorder[:mid])
        root.right = self.buildTree(inorder[mid+1:],postorder[mid:-1])

        return root

Python实现——哈希表优化

同样的，我们可以把中序遍历的值和索引放在一个哈希表中，这样就不需要通过遍历得到当前根结点在中序遍历中的位置了。

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:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
        # 辅助函数
        def helper(in_left,in_right,post_left,post_right):
            if in_left == in_right:
                return None

            # 构建当前“根”
            root = TreeNode(postorder[post_right-1])
            # 从哈希表中找到当前“根”的索引
            index = dicts[postorder[post_right-1]]

            # 更新中序遍历、后序遍历边界，然后递归构建左右子树
            # 我们可以通过“中序和后序个数是相同”这个隐含条件，求出后序左右边界
            root.left = helper(in_left,index,post_left,post_right-1-(in_right-index-1))
            root.right = helper(index+1,in_right,post_right-1-(in_right-index-1),post_right-1)

            return root

        # 哈希表存储中序遍历的值、索引
        dicts = {var:i for i,var in enumerate(inorder)}

        # 调用辅助函数
        root = helper(0,len(inorder),0,len(postorder))
        return root

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

题目描述

将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1。

示例:

给定有序数组: [-10,-3,0,5,9]，一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：

1
2
3
4
5
     0
    / \
  -3   9
  /   /
-10  5

思路

二叉搜索树的中序遍历刚好可以输出一个升序数组，所以题目给出的升序数组就是二叉搜索树的中序遍历。

根据中序遍历还原一颗树，又想到了 105 题 和 106 题，通过中序遍历加前序遍历或者中序遍历加后序遍历来还原一棵树。前序（后序）遍历的作用呢？提供根节点！然后根据根节点，就可以递归的生成左右子树。

这里的话怎么知道根节点呢？平衡二叉树，既然要做到平衡，我们只要把根节点选为数组的中点即可。

Python实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
        return self.binarySearch(nums,0,len(nums)-1)

    def binarySearch(self, nums, left, right):
        if left > right:
            return None

        mid = left + (right-left) // 2
        root = TreeNode(nums[mid])
        # 递归构建左右子树
        root.left = self.binarySearch(nums, left, mid-1)
        root.right = self.binarySearch(nums, mid+1, right)

        return root

109-有序链表转换二叉搜索树

题目描述

给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1。

示例:

给定的有序链表：[-10, -3, 0, 5, 9]，一个可能的答案是：[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树：

1
2
3
4
5
     0
    / \
  -3   9
  /   /
-10  5

思路

这道题目跟108题是类似的，数组可以很方便的找到中点，但链表的特性导致我们无法像数组那样通过下标访问各个元素。若想按照108题的做法，就需要设置两个指针slow、fast，slow每走一步fast走两步，这样fast结束时slow就在中点。但这样会导致每次递归都需要重复遍历链表，效率较低。

注意：当找到链表中的中间元素后，我们将链表从中间元素的左侧断开，做法是slow指针初始指向dummy，最后slow.next才是中点，然后我们在中点的左侧断开，也就是slow.next = None。

Python实现——二分

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:
    def sortedListToBST(self, head: ListNode) -> TreeNode:
        if head == None:
            return None

        # 链表寻找中点
        # 为了保证保留左子树的右边界，这里设置slow=dummy而不是head
        dummy = ListNode(None)
        dummy.next = head

        slow = dummy
        fast = head
        while fast.next != None and fast.next.next != None:
            slow = slow.next
            fast = fast.next.next

        # 由于slow初始值为dummy，因此slow.next才为中点
        root = TreeNode(slow.next.val)

        # 链表从中间断开（左子树的右边界是中点的左边一个节点，右子树的左边界是中点的右边一个节点）
        mid = slow.next.next
        slow.next = None
        
        # 递归构建左右子树
        # 判断左子树是否为空
        if slow == dummy:
            root.left = None
        else:
            root.left = self.sortedListToBST(dummy.next)
        root.right = self.sortedListToBST(mid)

        return root

Python实现——链表转换数组+二分

在这个方法中，我们将给定的链表转成数组并利用数组来构建二叉搜索树。数组找中间元素只需要 O(1) 的时间，所以会降低整个算法的时间复杂度开销。

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:
    def sortedListToBST(self, head: ListNode) -> TreeNode:
        # 链表转换成数组
        nums = []
        while head:
            nums.append(head.val)
            head = head.next

        return self.binarySearch(nums,0,len(nums)-1)

    # 辅助函数
    def binarySearch(self, nums, left, right):
        if left > right:
            return None

        mid = left + (right - left) // 2
        root = TreeNode(nums[mid])

        # 递归构建左右子树
        root.left = self.binarySearch(nums,left,mid-1)
        root.right = self.binarySearch(nums,mid+1,right)

        return root

二叉搜索树相关题目

二叉查找树既是一颗树，又带有特别的有序性质，所以考察的方式比较多而且灵活，属于面试题目中的常客。

此部分详细题解见：

参考

推荐文章
赞赏一杯咖啡
0%