LeetCode 872. Leaf-Similar Trees.java

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.

	/**
	* Definition for a binary tree node.
	* public class TreeNode {
	* int val;
	* TreeNode left;
	* TreeNode right;
	* TreeNode(int x) { val = x; }
	* }
	*/
	class Solution {
	public boolean leafSimilar(TreeNode root1, TreeNode root2) {
	List<Integer> lst1 = inOrder(root1);
	List<Integer> lst2 = inOrder(root2);
	if (lst1 == null && lst2 == null) {
	return true;
	}
	if (lst1 != null && lst2 == null) {
	return false;
	}
	if (lst1 == null && lst2 != null) {
	return false;
	}
	if (lst1.size() != lst2.size()) {
	return false;
	}
	for (int i = 0; i < lst1.size(); i++) {
	if (lst1.get(i) != lst2.get(i)) {
	return false;
	}
	}
	return true;
	}
	private List<Integer> inOrder(TreeNode root) {
	// corner cases
	if (root == null) {
	return new LinkedList<>();
	}
	List<Integer> lst = new LinkedList<>();
	if (root.left == null && root.right == null) {
	lst.add(root.val);
	return lst;
	}
	if (root.left != null) {
	lst.addAll(inOrder(root.left));
	}
	if (root.right != null) {
	lst.addAll(inOrder(root.right));
	}
	return lst;
	}
	}

view raw 872. Leaf-Similar Trees.java hosted with ❤ by GitHub