树

相关练习

LeetCode中相关的题目：

101. 对称二叉树
递归 O(n) O(n)

# 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 isSymmetric(self, root: TreeNode) -> bool:
        return self.isMirror(root,root)
    
    def isMirror(self, l: TreeNode, r: TreeNode) -> bool:
        ## l,r是两个指针，每次检查两个指针的值是否相同，如相等再判断左右子树是否对称
        ## 递归的终止天剑是两个节点都为空
        ## 或者两个节点有一个为空
        if l == None and r == None:
            return True
        if l == None or r == None:
            return False
        ## 两个根节点具有相同的值
        ## 每个树的右子树与另一个树的左子树镜像对称
        return l.val == r.val and self.isMirror(l.left,r.right) and self.isMirror(l.right,r.left)

迭代 O(n) O(n)

class Solution(object):
    def isSymmetric(self, root):
        ## 如果树为空，或者左子树右子树都为空，那么这也是对称的
        if not root or not (root.left or root.right):
            return True
        # 用队列保存节点，先将根节点的左子树根节点和右子树根节点放到队列中 
        queue = [root.left,root.right]
        while queue:
            # 从队列中取出两个节点，再比较这两个节点
            left = queue.pop(0)
            right = queue.pop(0)
            # 如果两个节点都为空就继续循环，两者有一个为空就返回false
            if not (left or right):
                continue
            if not (left and right):
                return False
            if left.val!=right.val: ## 如果两个值不相同，则不对称
                return False
            # 将左节点的左孩子， 右节点的右孩子放入队列
            queue.append(left.left)
            queue.append(right.right)
            # 将左节点的右孩子，右节点的左孩子放入队列
            queue.append(left.right)
            queue.append(right.left)
        return True

104. 二叉树的最大深度
二叉树的最大深度为max(l,r)+1
深度优先遍历：O(n) O(height)

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if root == None:
            return 0
        left = self.maxDepth(root.left)
        right = self.maxDepth(root.right)
        return max(left,right) + 1

广度优先遍历：O(n) O(n)

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if not root:
            return 0
        queue = collections.deque([root])  ## 队列
        depth = 0
        while queue: ## 队列为空，遍历完所有节点，循环结束
            n = len(queue) ## 计算当前节点所在树的层的宽度
            for i in range(n):
                node = queue.popleft() ## 把当前层的节点处队
                if node.left: ## 下一层的节点入队
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            depth += 1  ## 当前层遍历完则深度+1
        return depth

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

# 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 buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        def buildTree(pre_left,pre_right,in_left,in_right):
            if pre_left > pre_right:
                return None
            
            ## 前序遍历中第一个就是根节点
            pre_root = pre_left
            ## 查找根节点在中序遍历中的位置
            in_root = index[preorder[pre_root]]
            ## 建立根节点
            root = TreeNode(preorder[pre_root])
            ## 计算左子树的节点数目
            n_left = in_root - in_left
            ## 递归的建立左子树
            root.left = buildTree(pre_left+1,pre_left+n_left,in_left,in_root-1)
            ## 递归的建立右子树
            root.right = buildTree(pre_left+n_left+1,pre_right,in_root+1,in_right)

            return root
        
        n = len(preorder)
        ## 构建哈希映射，快速定位根节点的位置
        index = {element: i for i,element in enumerate(inorder)}
        return buildTree(0,n-1,0,n-1)

96. 不同的二叉搜索树: 满足数学公式

class Solution:
    def numTrees(self, n: int) -> int:
        c = 1
        for i in range(n):
            c = c * 2*(2*i+1)/(i+2)  ## 卡塔兰数公式
        return int(c)