Title: Leaf-Similar TreesSource: leetcode.com
Consider all the leaves of a binary tree. From left to right order, the values of those leaves form a leaf value sequence.
Leaves in a tree
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.
Python solution
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
''' https://leetcode.com/problems/leaf-similar-trees/ ''' # Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution(object): def findLeaves(self, root, leaves): if not root.left and not root.right: leaves.append(root.val) return if root.left: self.findLeaves(root.left, leaves) if root.right: self.findLeaves(root.right, leaves) def leafSimilar(self, root1, root2): """ :type root1: TreeNode :type root2: TreeNode :rtype: bool """ leaves1 = [] leaves2 = [] self.findLeaves(root1, leaves1) self.findLeaves(root2, leaves2) i = 0 ln = len(leaves1) while i < ln and leaves1[i] == leaves2[i]: i += 1 if i < ln: return False return True |
Java solution
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 |
/* https://leetcode.com/problems/leaf-similar-trees/description/ */ import java.util.List; import java.util.ArrayList; public class LeafSimilarTrees { public static void main(String[] args) { TreeNode root = new TreeNode(3); root.left = new TreeNode(5); root.right = new TreeNode(1); root.left.left = new TreeNode(6); root.left.right = new TreeNode(2); root.left.right.left = new TreeNode(7); root.left.right.right = new TreeNode(4); root.right.left = new TreeNode(9); root.right.right = new TreeNode(8); LeafSimilarTrees l = new LeafSimilarTrees(); System.out.println(l.leafSimilar(root, root)); } public boolean leafSimilar(TreeNode root1, TreeNode root2) { List<Integer> a = getLeafValueSequence(root1); List<Integer> b = getLeafValueSequence(root2); System.out.println(a); System.out.println(b); return a.equals(b); } private List<Integer> getLeafValueSequence(TreeNode root) { List<Integer> list = new ArrayList<>(); helper(root, list); return list; } private void helper(TreeNode root, List<Integer> seq) { if(root == null) return; helper(root.left, seq); if(root.left==null && root.right==null) seq.add(root.val); helper(root.right, seq); } } class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } } |