剑指offer经典题目

Question

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

例如，给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]

示例 1:

1
2
3

输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出: 3
解释: 节点 5 和节点 1 的最近公共祖先是节点 3。

示例 2:

1
2
3

输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出: 5
解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。

说明：所有节点的值都是唯一的。p、q 为不同节点且均存在于给定的二叉树中。

Intuition

如果有指向父节点的指针，直接一路回溯就能得到root到node的一条链表，两个node就能得到两条链表，找两条链表上最近的公共系节点，就是最近公共祖先。

如果没有指向父节点的指针，从root开始一路深度优先遍历，拿到root到node的一条链表，两个node就能得到两条链表，找两条链表上最近的公共系节点，就是最近公共祖先。

Code

import unittest
from typing import List

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


# 普通二叉树按照root/left/right的顺序进行进行构建树，不对数值大小进行对比。
class BinaryTree():

    # 创建二叉树 同样的一些数字，以不同的顺序输入，会影响二叉搜索树的创建。 index为要插入的位置。
    def Create(self, items):
        if len(items) == 0:  return None
        nodeQueue = []  # nodeQueue保存的是这一层所有非空节点，要留着给下一层创建左右子树的时候用。
        root = TreeNode(items[0])  # 创建一个根节点
        nodeQueue.append(root)  # 将根节点加入队列
        cur = None
        lineNodeNum = 2  # 记录下一层需要填充的节点的数量（注意不一定是2的幂，而是上一行中非空节点的数量乘2），第二层的节点数肯定是1*2。
        startIndex = 1  # 记录当前行中数字在数组中的开始位置，第0个位置在根节点，则第第二行第一个位置肯定是items[1]。
        restLength = len(items) - 1  # 记录数组中除去根节点剩余的元素的数量。
        while restLength > 0:  # 只要还有剩，就要继续添加。  
            i = startIndex
            while i < startIndex + lineNodeNum:  # 一次while循环会处理掉一个layer。
                if i == len(items):  return root  # 说明已经将nums中的数字用完，此时应停止遍历，并可以直接返回root
                cur = nodeQueue.pop(0)  # cur是上一行的根节点。
                if items[i] != None:  # 如果是None，就不做处理，保留左节点为None的情况。
                    cur.left = TreeNode(items[i])
                    nodeQueue.append(cur.left)

                if i + 1 == len(items):  return root  # 同上，做一个边界判定。
                if items[i + 1] != None:  # 同上，如果是None，就不做处理，保留右节点为None的情况。
                    cur.right = TreeNode(items[i + 1])
                    nodeQueue.append(cur.right)
                i += 2
            startIndex += lineNodeNum  # 加上这一层已经处理掉的数字，就是下一层要处理的数字的起点。
            restLength -= lineNodeNum  # 减去这一层已经处理掉的数字，就是剩余还未处理的数字的个数。
            lineNodeNum = len(nodeQueue) * 2  # nodeQueue的长度就是这一层的非空节点的个数，乘以2就是下一层需要填充的节点的数量。
        return root


    # 递归 前序遍历，根结点 ---> 左子树 ---> 右子树。
    def PreOrder(self, root):
        """
        Pre-Order Traversal of binary tree
        :param root: root node of target binary tree
        :return: TreeNode
        """
        # if not root:  return []  # 不处理None模式的一行代码
        if not root:  return [None]  # 不处理None模式的一行代码
        res = [root.val]
        left_tree = self.PreOrder(root.left)
        right_tree = self.PreOrder(root.right)
        return res + left_tree + right_tree   # 如果是递归调用二叉（搜索）树，前/中/后序遍历只用改这里的顺序就行。


class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if root == None:  return None
        res = []
        def _dfs(path=[], node=None, value=None):
            if node.val == value:
                res.append(path[:] + [node])
                return True
            if node.left:
                if _dfs(path + [node], node.left, value):
                    return True
            if node.right:
                if _dfs(path + [node], node.right, value):
                    return True
            return False

        # 找到root到输入节点的链表
        value = p.val
        _dfs([], root, value)
        value = q.val
        _dfs([], root, value)
        line_1 = res[0]
        line_2 = res[1]

        # 找链表上的公共节点
        count = 0
        public_node = None
        while count < len(line_1) and count < len(line_2):
            if line_1[count].val == line_2[count].val:
                public_node = line_1[count]
                count += 1
            else:
                break

        # 返回的不是int是TreeNode
        return public_node


class TestSolution(unittest.TestCase):
    def setUp(self):
        self.test_class = Solution()

    def test_solution(self):
        roots = [
            [3, 5, 1, 6, 2, 0, 8, None, None, 7, 4],  # 功能测试
            [3, 5, 1, 6, 2, 0, 8, None, None, 7, 4],  # 功能测试
                                                      # 边界值的测试
            []                                        # 特殊样例
        ]
        p = [5, 5, 6]
        q = [1, 4, 1]
        answers = [3, 5, None]
        res = []
        bTree = BinaryTree()
        for i in range(len(roots)):
            root = bTree.Create(roots[i])
            _p = TreeNode(p[i])
            _q = TreeNode(q[i])
            res_node = self.test_class.lowestCommonAncestor(root, _p, _q)
            if res_node:
                res.append(res_node.val)
            else:
                res.append(None)
        self.assertEqual(res, answers)
 
    def tearDown(self):
        del self.test_class


if __name__ == "__main__":
    unittest.main()

Extension

Question

剑指offer 面试题68 - I. 二叉搜索树的最近公共祖先（易） & LeetCode 235. 二叉搜索树的最近公共祖先（易）

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。” 例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]

示例 1:

1 2	`输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8 输出: 6`

解释: 节点 2 和节点 8 的最近公共祖先是 6。

示例 2:

1 2	`输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4 输出: 2`

解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。

说明：所有节点的值都是唯一的。p、q 为不同节点且均存在于给定的二叉搜索树中。

Intuition

二又搜索树是排序过的，位于左子树的节点都比父节点小，而位于右子树的节点都比父节点大，我们只需要从树的根节点开始和两个输入的节点进行比较。如果当前节点的值比两个节点的值都大，那么最低的共同父节点一定在当前节点的左子树中，于是下一步遍历当前节点的左子节点。如果当前节点的值比两个节点的值都小，那么最低的共同父节点一定在当前节点的右子树中，于是下一步遍历当前节点的右子节点。这样，在树中从上到下找到的第一个在两个输入节点的值之间的节点就是最低的公共祖先。

Code

# 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':
        self.res = None
        def _dfs(path=[], node=None):
            if samll <= node.val <= big:
                self.res = node
                return True

            # 如果当前节点的值小于small（node.val < small），就不用去左子树中查找了。
            if node.val >= samll and node.left:
                if _dfs(path + [node], node.left):
                    return True

            # 如果当前节点的值大于big（node.val > big），就不用去右子树中查找了。
            if node.val <= big or node.right:
                if _dfs(path + [node], node.right):
                        return True
                
            return False
        
        # 基于深度优先遍历，在树中从上到下找到的第一个在两个输入节点的值之间的节点就是最低的公共祖先。
        big = p.val if p.val > q.val else q.val
        samll = p.val if p.val < q.val else q.val
        _dfs([], root)

        return self.res

LeetCode 剑指offer

树

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议，转载请注明出处！

面试题36. 二叉搜索树与双向链表（中）& LeetCode 426. 将二叉搜索树转化为排序的双向链表（中）上一篇

剑指offer 面试题35. 复杂链表的复制（中）& LeetCode 138. 复制带随机指针的链表（中）下一篇

LeetCode 236. 二叉树的最近公共祖先（中）& 剑指offer 面试题68 - II. 二叉树的最近公共祖先（易）

Question

Intuition

Code

Extension