最近重新復(fù)習(xí)數(shù)據(jù)結(jié)構(gòu)级及，先從二叉樹開始刷題

樹的定義

先看一下在leetcode中對樹的定義：

二叉樹

把它叫做「樹」是因為它看起來像一棵倒掛的樹，也就是說它是根朝上额衙，而葉朝下的饮焦。

它具有以下的特點：

• 每個節(jié)點都只有有限個子節(jié)點或無子節(jié)點；
• 沒有父節(jié)點的節(jié)點稱為根節(jié)點窍侧；
• 每一個非根節(jié)點有且只有一個父節(jié)點县踢；
• 除了根節(jié)點外，每個子節(jié)點可以分為多個不相交的子樹伟件；
• 樹里面沒有環(huán)路硼啤。

樹的數(shù)據(jù)結(jié)構(gòu)

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        # 樹的左孩子
        self.left = None
       # 樹的右孩子
        self.right = None

二叉樹的遞歸模板

void traverse(TreeNode root) {
    // 前序遍歷
    traverse(root.left)
    // 中序遍歷
    traverse(root.right)
    // 后序遍歷
}

144. 二叉樹的前序遍歷

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def __init__(self):
        self.res = []
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        if not root:
            return []
        
        self.res.append(root.val)
        self.preorderTraversal(root.left)
        self.preorderTraversal(root.right)

        return self.res

94. 二叉樹的中序遍歷

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def __init__(self):
        self.res = []
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        if not root:
            return []

        
        self.inorderTraversal(root.left)
        self.res.append(root.val)
        self.inorderTraversal(root.right)

        return self.res

145. 二叉樹的后序遍歷

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def __init__(self):
        self.res = []
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        if not root:
            return []
        
        self.postorderTraversal(root.left)
        self.postorderTraversal(root.right)
        self.res.append(root.val)

        return self.res