872. Leaf-Similar Trees

Leetcode 链接

题目

Consider all the leaves of a binary tree. From left to right order, the values of those leaves form a leaf value sequence.

For example, in the given tree above, the leaf value sequence is (6, 7, 4, 9, 8).

Two binary trees are considered leaf-similar if their leaf value sequence is the same.

Return true if and only if the two given trees with head nodes root1 and root2 are leaf-similar.

Note:

Both of the given trees will have between 1 and 100 nodes.

题意解析

给出两棵树，判断两棵树的叶子节点从左到右的序列是否一致。

解决方案

只要分别求出两棵树的叶子节点序列，然后进行比较即可。

Go 代码

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func leafSimilar(root1 *TreeNode, root2 *TreeNode) bool {
    arr1 := make([]int, 0)
    dfs(root1, &arr1)

    arr2 := make([]int, 0)
    dfs(root2, &arr2)

    if len(arr1) != len(arr2) {
        return false
    }

    for i := range arr1 {
        if arr1[i] != arr2[i] {
            return false
        }
    }

    return true
}

func dfs(root *TreeNode, arr *[]int) {
    if root == nil {
        return 
    }

    if isLeaf(root) {
        *arr = append(*arr, root.Val)
        return
    }

    dfs(root.Left, arr)
    dfs(root.Right, arr)
}

func isLeaf(root *TreeNode) bool {
     return root != nil && root.Left == nil && root.Right == nil
}