LeetCode0872: 叶子相似的树

题目介绍

描述：

请考虑一颗二叉树上所有的叶子，这些叶子的值按从左到右的顺序排列形成一个叶值序列。

举个例子，如上图所示，给定一颗叶值序列为 (6, 7, 4, 9, 8) 的树。

如果有两颗二叉树的叶值序列是相同，那么我们就认为它们是叶相似的。

如果给定的两个头结点分别为 root1 和 root2 的树是叶相似的，则返回 true；否则返回 false 。

提示：

给定的两颗树可能会有 1 到 200 个结点。给定的两颗树上的值介于 0 到 200 之间。

解题思路：

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

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

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

二叉树解题策略

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

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

得到两棵树的叶值序列，然后比较是否相等

自己的解法实现

def leafSimilar4(self, root1, root2):
        def dfs(node, res):
            if not node: return     # 如果根节点为空就结束这个
            if not node.left and not node.right:
                # 如果没有左右孩子就把它加进去
                res += [node.val]
            else:    # 有左孩子或者右孩子就遍历
                dfs(node.left, res)
                dfs(node.right, res)
            return res
        num1 = []
        num2 = []
        return dfs(root1, num1) == dfs(root2, num2)

网上比较优秀的解法

解法一

方法：深度优先搜索首先，让我们找出给定的两个树的叶值序列。之后，我们可以比较它们，看看它们是否相等。

要找出树的叶值序列，我们可以使用深度优先搜索。如果结点是叶子，那么 dfs 函数会写入结点的值，然后递归地探索每个子结点。这可以保证按从左到右的顺序访问每片叶子，因为在右孩子结点之前完全探索了左孩子结点。

def leafSimilar(self, root1, root2):
        def dfs(node):
            if node:
                if not node.left and not node.right:
                    yield node.val
                yield from dfs(node.left)
                yield from dfs(node.right)
        return list(dfs(root1)) == list(dfs(root2))

解法二

定义先序遍历函数，返回叶值序列。并判断两个数root1和root2返回的叶值序列是否相同。

def leafSimilar2(self, root1, root2):
        def preorder(node, leaf_list):
            if not node: return None
            if not node.left and not node.right:
                leaf_list.append(node.val)
            preorder(node.left, leaf_list)
            preorder(node.right, leaf_list)
            return leaf_list
        return preorder(root1, []) == preorder(root2, [])

解法三

递归方法

def leafSimilar3(self, root1, root2):
        num1 = []
        num2 = []
        def getleaves(node, nums):
            if node and (not node.left and not node.right):
                nums.append(node.val)
            if node.left:
                getleaves(node.left, nums)
            if node.right:
                getleaves(node.right, nums)
            return nums
        return getleaves(root1, num1) == getleaves(root2, num2)