二叉树

定义

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

高度：该结点到叶子结点

深度：根结点到该结点

种类

满二叉树

如果一棵二叉树只有度为 0 的结点和度为 2 的结点，并且度为 0 的结点在同一层上，则这棵二叉树为满二叉树

完全二叉树

在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2^(h-1) 个节点

二叉搜索树

若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值

若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值

它的左、右子树也分别为二叉排序树

平衡二叉搜索树

它是一棵空树或它的左右两个子树的高度差的绝对值不超过 1，并且左右两个子树都是一棵平衡二叉树

遍历方式

深度优先遍历

先往深走，遇到叶子节点再往回走

• 144. 二叉树的前序遍历(中左右)
• 94. 二叉树的中序遍历(左中右)
• 145. 二叉树的后序遍历(左右中)

二叉树的前中后序遍历

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    # 前序
    def preorderTraversal(self, root: TreeNode):
        res = []

        def traversal(root: TreeNode):
            if not root:
                return
            res.append(root.val)  # 中
            traversal(root.left)  # 左
            traversal(root.right)  # 右
        traversal(root)
        return res

    # 中序
    def inorderTraversal(self, root: TreeNode):
        res = []

        def traversal(root: TreeNode):
            if not root:
                return
            traversal(root.left)  # 左
            res.append(root.val)  # 中
            traversal(root.right)  # 右
        traversal(root)
        return res

    # 后序
    def postorderTraversal(self, root: TreeNode):
        res = []

        def traversal(root: TreeNode):
            if not root:
                return
            traversal(root.left)  # 左
            traversal(root.right)  # 右
            res.append(root.val)  # 中
        traversal(root)
        return res

广度优先遍历

一层一层的去遍历

• 102. 二叉树的层序遍历

二叉树的层序遍历

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    def levelOrder(self, root: TreeNode):
        result = []
        if not root:
            return result
        from collections import deque
        que = deque([root])
        while que:
            size = len(que)
            res = []
            for _ in range(size):
                cur = que.popleft()
                res.append(cur.val)
                if cur.left:
                    que.append(cur.left)
                if cur.right:
                    que.append(cur.right)
            result.append(res)
        return result

• 107.二叉树的层次遍历 II
• 429. N 叉树的层序遍历

LeetCode

98. 验证二叉搜索树

验证二叉搜索树

# 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 isValidBST(self, root: TreeNode) -> bool:
        def traversal(root: TreeNode, pre_val: float("-inf")):
            if not root:
                return True
            left_bst = traversal(root.left, pre_val)  # 左
            if not left_bst:
                return False
            if root.val <= pre_val:
                return False
            else:
                pre_val = root.val
            return traversal(root.right, pre_val)  # 右
        return traversal(root, -100)

101. 对称二叉树

101. 对称二叉树

# 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:
        if not root:
            return True
        return self.compare(root.left, root.right)

    def compare(self, left, right):
        if left is None and right is not None:
            return False
        elif left is not None and right is None:
            return False
        elif left is None and right is None:
            return True
        elif left.val != right.val:
            return False

        outside = self.compare(left.left, right.right)
        inside = self.compare(left.right, right.left)
        return outside and inside

104. 二叉树的最大深度

104. 二叉树的最大深度

# 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
        left = self.maxDepth(root.left)
        right = self.maxDepth(root.right)
        return max(left, right) + 1

110. 平衡二叉树

110. 平衡二叉树

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

    def get_height(self, root: TreeNode):
        if not root:
            return 0
        left = self.get_height(root.left)
        if left == -1:
            return -1
        right = self.get_height(root.right)
        if right == -1:
            return -1
        if abs(left - right) > 1:
            return -1
        else:
            return 1 + max(left, right)

111. 二叉树的最小深度

111. 二叉树的最小深度

# 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 minDepth(self, root: TreeNode) -> int:
        if not root:
            return 0
        if not root.left and not root.right:
            return 1

        min_depth = float("inf")

        if root.left:
            min_depth = min(self.minDepth(root.left), min_depth)
        if root.right:
            min_depth = min(self.minDepth(root.right), min_depth)
        return min_depth + 1

222. 完全二叉树的节点个数

222. 完全二叉树的节点个数

# 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 countNodes(self, root: TreeNode) -> int:
        if not root:
            return 0

        left = self.countNodes(root.left)
        right = self.countNodes(root.right)
        return left + right + 1

226. 翻转二叉树

翻转二叉树

# 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 invertTree(self, root: TreeNode) -> TreeNode:
        if not root:
            return None
        root.left, root.right = root.right, root.left
        self.invertTree(root.left)
        self.invertTree(root.right)
        return root

257. 二叉树的所有路径

257. 二叉树的所有路径

# 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 binaryTreePaths(self, root: TreeNode):
        result = []
        path = ""
        if not root:
            return result
        self.traversal(root, path, result)
        return result

    def traversal(self, cur: TreeNode, path: str, result):
        path += str(cur.val)
        if not cur.left and not cur.right:
            result.append(path)
        if cur.left:
            self.traversal(cur.left, path + "->", result)
        if cur.right:
            self.traversal(cur.right, path + "->", result)

404. 左叶子之和

404. 左叶子之和

# 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 sumOfLeftLeaves(self, root: TreeNode) -> int:
        if not root:
            return 0
        if not root.left and not root.right:
            return 0
        left_val = self.sumOfLeftLeaves(root.left)
        if root.left and not root.left.left and not root.left.right:
            left_val = root.left.val
        right_val = self.sumOfLeftLeaves(root.right)
        return left_val + right_val

530. 二叉搜索树的最小绝对差

530. 二叉搜索树的最小绝对差

# 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 getMinimumDifference(self, root: TreeNode) -> int:
        res = []

        def build_list(root: TreeNode):
            if not root:
                return None
            if root.left:
                build_list(root.left)
            res.append(root.val)
            if root.right:
                build_list(root.right)
            return res

        build_list(root)
        min_val = float("inf")
        for i in range(len(res) - 1):
            min_val = min(abs(res[i] - res[i + 1]), min_val)
        return min_val

617. 合并二叉树

617. 合并二叉树

# 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

        root1.val += root2.val
        root1.left = self.mergeTrees(root1.left, root2.left)
        root1.right = self.mergeTrees(root1.right, root2.right)

        return root1

700. 二叉搜索树中的搜索

700. 二叉搜索树中的搜索

# 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 searchBST(self, root: TreeNode, val: int) -> TreeNode:
        if not root or root.val == val:
            return root
        if root.val > val:
            return self.searchBST(root.left, val)
        if root.val < val:
            return self.searchBST(root.right, val)