算法之二叉树篇

二叉树的层次遍历

题目描述

给定一个二叉树，返回其节点值自底向上的层次遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

示例

输入：给定二叉树 [3,9,20,null,null,15,7],

返回值：[[15,7],[9,20],[3]]

解题思路

使用nex保存每一层级的叶节点，使用tmp保存每一层级节点值，从上至下，每一层级从左至右遍历。最后将列表反转即可。

class TreeNode(object):
    """docstring for TreeNode"""
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution(object):
    """docstring for Solution"""
    def levelOrderBottom(self, root):
        if root == None: return []
        res = []
        def dfs(root):
            queue = [root]
            while queue:
                nex = []
                tmp = []
                for node in queue:
                    tmp.append(node.val)
                    if node.left:
                        nex.append(node.left)
                    if node.right:
                        nex.append(node.right)
                res.append(tmp)
                queue = nex
        dfs(root)
        return res[::-1]

node1 = TreeNode(1)
node2 = TreeNode(3)
node3 = TreeNode(4)
node1.left = None
node1.right = node2
node2.left = node3
node2.right = None

solution = Solution()
print(solution.levelOrderBottom(node1))

• 时间复杂度：O(n)
• 空间复杂度：O(n)

对称二叉树

题目描述

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

示例

输入：二叉树 [1,2,2,3,4,4,3] 是对称的。

返回值：True

输入：[1,2,2,null,3,null,3] 则不是镜像对称的。

返回值：False

解题思路

使用递归思想，如果左子树的左节点等于右子树的右节点且左子树的右节点等于右子树的左节点，则表示左右子树是对称的。

class TreeNode(object):
    """docstring for TreeNode"""
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution(object):
    """docstring for Solution"""
    def isSymmetric(self, root):
        def check(node1, node2):
            if not node1 and not node2:
                return True
            elif not node1 or not node2:
                return False
            if node1.val != node2.val:
                return False
            return check(node1.left, node2.right) and check(node1.right, node2.left)
        return check(root, root)

• 时间复杂度：O(n)
• 空间复杂度：O(n)

相同的树

题目描述

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

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

示例

输入：[1,2,3], [1,2,3]

返回值：True

输入：[1,2], [1,null,2]

返回值：False

解题思路

使用递归，判断两个二叉树的根节点一致，且左右子树一致即为相同的树。

class TreeNode(object):
    """docstring for TreeNode"""
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        if not p and not q: return True
        if p == None or q == None: return False
        if p.val == q.val:
            return self.isSameTree(p.left,q.left) and self.isSameTree(p.right,q.right)
        else:
            return False

• 时间复杂度：O(n)
• 空间复杂度：O(n)

二叉树的最大深度

题目描述

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

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

示例

输入：给定二叉树 [3,9,20,null,null,15,7]

返回值：3

解题思路

BFS广度优先搜索，使用双端队列deque（因为性能比另外两种Queue好得多），在大循环内对二叉树的每个层做一次遍历，range(len(queue))使只遍历当前的层，每次大循环ans加1。由于每个节点仅访问一次，所以时间复杂度O(n)

import collections

class TreeNode:
    """docstring for TreeNode"""
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution(object):
    """docstring for Solution"""
    def maxDepth(self, root):
        if not root: return 0
        queue = collections.deque()
        # deque的append：在列表右边添加一个元素
        queue.append(root)
        ans = 0
        while queue:
            ans += 1
            for i in range(len(queue)):
            # deque的popleft：在列表的左边弹出一个元素
                node = queue.popleft()
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
        return ans

• 时间复杂度：O(n)
• 空间复杂度：O(n)

平衡二叉树

题目描述

给定一个二叉树，判断它是否是高度平衡的二叉树（一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1）。

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

示例

输入：给定二叉树 [3,9,20,null,null,15,7]

返回值：true

解题思路1

自顶向下的递归。对于当前遍历到的节点，首先计算左右子树的高度，如果左右子树的高度差不超过1，再分别递归遍历左右子节点，并判断左子树和右子树是否平衡。

class TreeNode:
    """docstring for TreeNode"""
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution(object):
    """docstring for Solution"""
    def isBalanced(self, root):
        # 计算当前节点作为根节点时的高度
        def height(root):
            if not root: return 0
            return max(height(root.left), height(root.right))+1
        if not root: return True
        # 计算左右子树高度如果高度差不超过1，分别递归遍历左右子节点，判断左子树和右子树是否平衡
        return abs(height(root.left)-height(root.right))<=1 and self.isBalanced(root.left) and self.isBalanced(root.right)

• 时间复杂度：O(n^2)，n为二叉树中的节点个数
• 空间复杂度：O(n)

解题思路2

自低向上的递归，函数height不会被重复调用。对于当前遍历到的节点，首先递归地判断其左右子树是否平衡，再判断以当前节点为根的子树是否平衡。如果一棵树是平衡的，则返回其高度(高度肯定是大于等于0的)，否则返回-1。如果存在一个子树不平衡，则整个二叉树不平衡。

class TreeNode:
    """docstring for TreeNode"""
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution(object):
    """docstring for Solution"""
    def isBalanced(self, root):
        def height(root):
            if not root: return 0
            left_h = height(root.left)
            right_h = height(root.right)
            if left_h == -1 or right_h == -1 or abs(left_h-right_h)>1:
                return -1
            else:
                return max(left_h, right_h)+1
        return height(root)>=0

• 时间复杂度：O(n)，n为二叉树中的节点个数
• 空间复杂度：O(n)