LeetCode0865: 具有所有最深结点的最小子树

题目介绍

描述：

给定一个根为 root 的二叉树，每个结点的深度是它到根的最短距离。

如果一个结点在整个树的任意结点之间具有最大的深度，则该结点是最深的。

一个结点的子树是该结点加上它的所有后代的集合。

返回能满足“以该结点为根的子树中包含所有最深的结点”这一条件的具有最大深度的结点。

解题思路：

递归算法的关键是要明确函数的「定义」是什么，然后相信这个定义，利用这个定义推导最终结果。

写树相关的算法，简单说就是，先搞清楚当前 root 节点该做什么，然后根据函数定义递归调用子节点，递归调用会让孩子节点做相同的事情。

二叉树题目的一个难点在于如何通过题目的要求思考出每一个节点需要做什么

二叉树解题策略

一递归二队列 + 迭代（层次遍历）三栈 + 迭代（非递归遍历）四其它

三种基本的遍历方式，都可以用递归来实现。写递归算法的时候，需要注意递归退出条件以及递归操作的表达。

自己的解法实现

def subtreeWithAllDeepest4(self, root):
        def dfs(node):
            if not node:
                return None, 0
            left, i = dfs(node.left)
            right, j = dfs(node.right)
            if i > j:
                return left, i + 1
            elif j > i:
                return right, j + 1
            return node, i + 1

        return dfs(root)[0]

网上比较优秀的解法

解法一

方法一：两次深度优先搜索思路最直白的做法，先做一次深度优先搜索标记所有节点的深度来找到最深的节点，再做一次深度优先搜索用回溯法找最小子树。定义第二次深度优先搜索方法为 answer(node)，每次递归有以下四种情况需要处理：

如果 node 没有左右子树，返回 node。
如果 node 左右子树的后代中都有最深节点，返回 node。
如果只有左子树或右子树中有且拥有所有的最深节点，返回这棵子树的根节点（即 node 的左/右孩子）。
否则，当前子树中不存在答案。

算法先做一次深度优先搜索标记所有节点的深度，再做一次深度优先搜索找到最终答案。

def subtreeWithAllDeepest(self, root):
        # Tag each node with it's depth.
        depth = {None: -1}
        def dfs(node, parent = None):
            if node:
                depth[node] = depth[parent] + 1
                dfs(node.left, node)
                dfs(node.right, node)
        dfs(root)

        max_depth = max(depth.itervalues())

        def answer(node):
            # Return the answer for the subtree at node.
            if not node or depth.get(node, None) == max_depth:
                return node
            L, R = answer(node.left), answer(node.right)
            return node if L and R else L or R
        return answer(root)

解法二

方法二：一次深度优先搜索思路可以把方法一中两次深度优先搜索合并成一次，定义方法 dfs(node)，与方法一中不同的是 dfs(node) 返回两个值，子树中的答案和 node 节点到最深节点的距离。

算法 dfs(node) 返回的结果有两个部分：

Result.node：包含所有最深节点的最小子树的根节点。
Result.dist：node 到最深节点的距离。分别计算 dfs(node) 的两个返回结果：

对于 Result.node：如果只有一个 childResult 具有最深节点，返回 childResult.node。

如果两个孩子都有最深节点，返回 node。

Result.dist 为 childResult.dist 加 1。

def subtreeWithAllDeepest2(self, root):
        import collections
        Result = collections.namedtuple("Result", ("node", "dist"))
        def dfs(node):
            if not node: return Result(None, 0)
            L, R = dfs(node.left), dfs(node.right)
            if L.dist > R.dist:
                return Result(L.node, L.dist + 1)
            if L.dist < R.dist:
                return Result(R.node, R.dist + 1)
            return Result(node, L.dist + 1)
        return dfs(root).node

解法三

利用递归的思想。首先，要明确只有当左子树和右子树的深度相同时，我们才返回以当前结点为根的子树！，否则递归深度更深的左右子树。

def depth(self, tree): #    计算树的深度
        if tree == None:
            return 1
        return max(self.depth(tree.left), self.depth(tree.right)) + 1
    def subtreeWithAllDeepest3(self, root):
        left_depth = self.depth(root.left)
        rigth_depth = self.depth(root.right)
        if left_depth == rigth_depth:
            return root
        else:
            return self.subtreeWithAllDeepest(root.left) if left_depth > rigth_depth else self.subtreeWithAllDeepest(root.right)