## Algorithm

Problem Name: 872. 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: root1 = [1,2,3], root2 = [1,3,2]
Output: false

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].

## Code Examples

### #1 Code Example with C++ Programming

Code - C++ Programming

class Solution {
public:
bool leafSimilar(TreeNode* root1, TreeNode* root2) {
vector<int>v;
int pos = 0;
dfs(root1, v, pos);
pos = 0;
return dfs(root2, v, pos);
}

bool dfs(TreeNode* p, vector<int>& v, int& pos){
if(!p) return true;
if(!p->left && !p->right){
if(v.size() == pos) v.push_back(p->val);
return v[pos++] == p->val;
}
return dfs(p->left, v, pos) && dfs(p->right, v, pos);
}
};
Copy The Code &

Input

cmd
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

cmd
true

### #2 Code Example with Java Programming

Code - Java Programming

class Solution {
public boolean leafSimilar(TreeNode root1, TreeNode root2) {
StringBuilder leavesOne = new StringBuilder();
StringBuilder leavesTwo = new StringBuilder();
populateLeaves(root1, leavesOne);
populateLeaves(root2, leavesTwo);
return leavesOne.toString().equals(leavesTwo.toString());
}

private void populateLeaves(TreeNode root, StringBuilder leaves) {
if (root == null) {
return;
}
if (root.left == null && root.right == null) {
leaves.append(root.val).append(",");
return;
}
populateLeaves(root.left, leaves);
populateLeaves(root.right, leaves);
}
}
Copy The Code &

Input

cmd
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

cmd
true

### #3 Code Example with Python Programming

Code - Python Programming

class Solution:
def leafSimilar(self, root1, root2):
def dfs(node, arr):
if node:
if not node.left and not node.right: arr += [node.val]
dfs(node.left, arr)
dfs(node.right, arr)
return arr
return dfs(root1, []) == dfs(root2, [])
Copy The Code &

Input

cmd
root1 = [1,2,3], root2 = [1,3,2]

Output

cmd
false

### #4 Code Example with C# Programming

Code - C# Programming

using System.Collections.Generic;
using System.Linq;

namespace LeetCode
{
public class _0872_LeafSimilarTrees
{
public bool LeafSimilar(TreeNode root1, TreeNode root2)
{
var leaves1 = new List < int>();
var leaves2 = new List<int>();

InOrder(root1, leaves1);
InOrder(root2, leaves2);

return leaves1.SequenceEqual(leaves2);
}

private void InOrder(TreeNode node, IList < int> leaves)
{
if (node == null) return;
if (node.left == null && node.right == null)
{
return;
}

InOrder(node.left, leaves);
InOrder(node.right, leaves);
}
}
}
Copy The Code &

Input

cmd
root1 = [1,2,3], root2 = [1,3,2]

Output

cmd
false