中等难度-树类型-未具体分类问题

来源于leetcode题库94,236

94.二叉树的中序遍历

题目描述：
- 给定一个二叉树，返回它的中序遍历
示例：

略

题解：
- 参考题解区大佬henry的颜色标记法，如有侵扰，烦请联系删除

# 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.二叉树的最近公共祖先

题目描述：
- 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
  最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
示例：

略

题解
- 题解来源于题解区大佬krahets,如有侵扰烦请联系删除

# 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的左或右子树中
        递归对二叉树后序遍历，遇到p或q时返回。从底至顶回溯
        当节点p，q在root的两侧时，节点root即为最近公共祖先，向上返回root
        终止条件：
            越过叶节点，返回null，root等于p,q，直接返回root
        递推：
            递归左子节点，返回值记为left
            递归右子节点，返回值记为right
        返回值：
            1.left和right都为空，返回null
            2.left各right都不为空，p，q在root的两侧，返回root
            3.left为空，right不为空，p，q都不在root的左子树，返回right：
                (1)p，q其中一个在root的右子树上，此时right指向p或者q
                (2)p，q都在root的右子树上，此时right指向最近公共祖先节点
            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

最后编辑于：2020.08.30 22:33:35