Leaf Similar Trees Solution - Leetcode
Leetcode Solution: Understand and solve Leetcode problem Leaf Similar Trees(836)
In this article, we’ll be solving the problem: Leaf Similar Trees . This problem belongs to Tree Traversal and Recursion category.
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.
Constraints:
Both of the given trees will have between 1 and 200 nodes.
Both of the given trees will have values between 0 and 200
Here, the input contains the reference to the root of two binary trees. We have to check if the leaf nodes from first trees appear in the same order in the second tree or not.
To solve this problem, I’ll be using the pre order tree traversal approach(once again). While traversing each of the nodes of the first tree, I’ll be collecting the values of all the leaf nodes in a list. The list will maintain the order of insertion here, so the last found node will be at the last index.
Once the traversal for the first tree is complete, I’ll start the traversal for the second tree. If both the trees are
leaf similar then they both will have the same leaf nodes at the same index in the list. So, while traversing the nodes
in the second tree if I find a leaf node, I’ll check for its existence in the list at index 0. If that’s present, I’ll
increase the current list index by 1 so that we do the value comparison at the next index. If the values do not match
then the traversal will be exited and false will be sent back.
Here, in this image you can see that the 3rd leaf node did not match the 3rd element from the list. At this point we just return false.
Adding the code for solution that can found here on GitHub as well:
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
var leaves []int
var index int
func leafSimilar(root1 *TreeNode, root2 *TreeNode) bool {
leaves = []int{}
index = 0
// false is returned if both the tress are not non nil
if !(root1 != nil && root2 != nil) {
return false
}
// preOrder fills up the leaves list after traversing
// the first tree
preOrder1(root1)
// fmt.Println(leafs)
return preOrder2(root2)
}
// addLeaf appends the passed value into the leaves list
func addLeaf(value int) {
leaves = append(leaves, value)
}
// checkLeaf checks whether the element at the next index
// matches with the passed value
func checkLeaf(value int) bool {
index++
if index == len(leafs) + 1{
return false
}
return leafs[index-1] == value
}
// preOrder1 traverses over the first tree
// and fills up the leaves list
func preOrder1(node *TreeNode) {
if node.Left != nil {
preOrder1(node.Left)
}
if node.Right != nil {
preOrder1(node.Right)
}
if node.Left == nil && node.Right == nil {
addLeaf(node.Val)
}
}
// preOrder2 traverses over the second tree
// and checks if the leaf node values are present
// in the leaves list
func preOrder2(node *TreeNode) bool {
if node.Left != nil {
equal := preOrder2(node.Left)
if !equal {
return false
}
}
if node.Right != nil {
equal := preOrder2(node.Right)
if !equal {
return false
}
}
if node.Left == nil && node.Right == nil {
return checkLeaf(node.Val)
}
return true
}
