872.Leaf-Similar Trees
===

###### tags: `Easy`,`Tree`,`Binary Tree`,`DFS`

[872. Leaf-Similar Trees](https://leetcode.com/problems/leaf-similar-trees/)

### 題目描述

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.

### 範例

**Example 1:**


Input: root1 = [3,5,1,6,2,9,8,null,null,7,4], root2 = [3,5,1,6,7,4,2,null,null,null,null,null,null,9,8]
Output: true

**Example 2:**


Input: root = [5,1,4,null,null,3,6]
Output: false
Explanation: The root node's value is 5 but its right child's value is 4.

**Constraints**:

* The number of nodes in each tree will be in the range `[1, 200]`.
* Both of the given trees will have values in the range `[0, 200]`.

### 解答

#### C#

public class Solution {
    public bool LeafSimilar(TreeNode root1, TreeNode root2) {
        var list1 = PreorderLeaves(root1).GetEnumerator();
        var list2 = PreorderLeaves(root2).GetEnumerator();
        
        while (list1.MoveNext()) {
            if (!list2.MoveNext() || 
                list1.Current != list2.Current) {
                return false;
            }
        }
        if (list2.MoveNext()) return false;
        return true;
    }

    private IEnumerable<int> PreorderLeaves(TreeNode root) {
        var stack = new Stack<TreeNode>();
        stack.Push(root);

        while (stack.Count > 0) {
            var node = stack.Pop();
            if (node.left == null && node.right == null) {
                yield return node.val;
            }
            if (node.right != null) {
                stack.Push(node.right);
            }
            if (node.left != null) {
                stack.Push(node.left);
            }
        }
    }

遞迴版本

public class Solution {
    public bool LeafSimilar(TreeNode root1, TreeNode root2) {
        return Dfs(root1).SequenceEqual(Dfs(root2));
    }

    private IEnumerable<int> Dfs(TreeNode node) {
        if (node.left == null && node.right == null) {
            yield return node.val;
        }
        if (node.left != null) {
            foreach (int val in Dfs(node.left)) {
                yield return val;
            }
        }
        if (node.right != null) {
            foreach (int val in Dfs(node.right)) {
                yield return val;
            }
        }
    }
}

>[name=Jim][time= Dec 8, 2022]

#### Python

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def leafSimilar(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:
        def findLeaf(root):
            res, l_res, r_res = [], [], []
            
            if not root.left and not root.right:
                res.append(root.val)

            if root.left:
                l_res = findLeaf(root.left)
            if root.right:
                r_res = findLeaf(root.right)

            return res + l_res + r_res

        return findLeaf(root1) == findLeaf(root2)

>[name=Kobe][time= Dec 8, 2022]

class Solution:
    def leafSimilar(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:
        def dfs(root):
            if root:
                if not root.left and not root.right:
                    yield root.val
                for v in dfs(root.left):
                    yield v
                for v in dfs(root.right):
                    yield v
        return list(dfs(root1)) == list(dfs(root2))

> [name=Yen-Chi Chen][time=Thu, Dec 8, 2022]

#### C++

class Solution {
public:
    void dfs(TreeNode* root, vector<int>& leaves) {
        if (!root) return;
        if (!root->left && !root->right) leaves.push_back(root->val);
        dfs(root->left, leaves);
        dfs(root->right, leaves);
    }
    bool leafSimilar(TreeNode* root1, TreeNode* root2) {
        vector<int> leaves1, leaves2;
        dfs(root1, leaves1);
        dfs(root2, leaves2);
        return leaves1 == leaves2;
    }
};

> [name=Yen-Chi Chen][time=Thu, Dec 8, 2022]

#### Javascript

function leafSimilar(root1, root2) {
  return findLeaf(root1).toString() === findLeaf(root2).toString();
}

function findLeaf(root) {
  const leaf = [];
  if (root === null) return leaf;

  if (root.left === null && root.right === null) {
    leaf.push(root.val);
  }

  leaf.push(...findLeaf(root.left));
  leaf.push(...findLeaf(root.right));

  return leaf;
}

>[name=Marsgoat][time= Dec 8, 2022]

### Reference

[回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)