• 來源于leetcode題庫94,236

94.二叉樹的中序遍歷

• 題目描述：
  • 給定一個(gè)二叉樹，返回它的中序遍歷
• 示例：

略

• 題解：
  • 參考題解區(qū)大佬henry的顏色標(biāo)記法，如有侵?jǐn)_，煩請(qǐng)聯(lián)系刪除

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

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        #白色的是未訪問的，灰色的是已訪問過的
        WHITE, GRAY = 0, 1
        res = []
        stack = [(WHITE, root)]
        while stack:
            color, node = stack.pop()
            if node is None: 
                continue
            if color == WHITE:
                stack.append((WHITE, node.right))
                stack.append((GRAY, node))
                stack.append((WHITE, node.left))
            else:
                res.append(node.val)
        return res

236.二叉樹的最近公共祖先

• 題目描述：

  • 給定一個(gè)二叉樹, 找到該樹中兩個(gè)指定節(jié)點(diǎn)的最近公共祖先。
    最近公共祖先的定義為：“對(duì)于有根樹 T 的兩個(gè)結(jié)點(diǎn) p、q，最近公共祖先表示為一個(gè)結(jié)點(diǎn) x，滿足 x 是 p、q 的祖先且 x 的深度盡可能大（一個(gè)節(jié)點(diǎn)也可以是它自己的祖先）?！?/li>

• 示例：

略

• 題解
  • 題解來源于題解區(qū)大佬krahets,如有侵?jǐn)_煩請(qǐng)聯(lián)系刪除

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

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        '''
        root是p,q的最近公共祖先，則：可能為以下情況
        1.p,q在root的子樹中，且分別在左右子樹中
        2.p=root，且q在root的左或右子樹中
        3.q=root，且p在root的左或右子樹中
        遞歸對(duì)二叉樹后序遍歷，遇到p或q時(shí)返回。從底至頂回溯
        當(dāng)節(jié)點(diǎn)p，q在root的兩側(cè)時(shí)，節(jié)點(diǎn)root即為最近公共祖先，向上返回root
        終止條件：
            越過葉節(jié)點(diǎn)，返回null，root等于p,q，直接返回root
        遞推：
            遞歸左子節(jié)點(diǎn)，返回值記為left
            遞歸右子節(jié)點(diǎn)，返回值記為right
        返回值：
            1.left和right都為空，返回null
            2.left各right都不為空，p，q在root的兩側(cè)，返回root
            3.left為空，right不為空，p，q都不在root的左子樹，返回right：
                (1)p，q其中一個(gè)在root的右子樹上，此時(shí)right指向p或者q
                (2)p，q都在root的右子樹上，此時(shí)right指向最近公共祖先節(jié)點(diǎn)
            4.left不為空，right為空，與3同理
        '''
        if not root or root == p or root == q:
            return root
        left = self.lowestCommonAncestor(root.left,p,q)
        right = self.lowestCommonAncestor(root.right,p,q)
        # 情況1
        if not left and not right :
            return 
        # 情況3
        if not left:
            return right
        # 情況4
        if not right:
            return left
        # 情況2
        if left and right:
            return root