原题链接在这里：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.
Note:
1 and 100 nodes.题解：
Use pre-order to get leaf one by one and compare the value.
Time Complexity: O(n). n is tree size.
Space: O(h). h is tree height.
AC Java:
1 /** 2 * Definition for a binary tree node. 3 * public class TreeNode { 4 * int val; 5 * TreeNode left; 6 * TreeNode right; 7 * TreeNode(int x) { val = x; } 8 * } 9 */ 10 class Solution { 11 public boolean leafSimilar(TreeNode root1, TreeNode root2) { 12 if(root1 == null || root2 == null){ 13 return root1 == root2; 14 } 15 16 Stack<TreeNode> stk1 = new Stack<>(); 17 Stack<TreeNode> stk2 = new Stack<>(); 18 stk1.push(root1); 19 stk2.push(root2); 20 while(!stk1.isEmpty() && !stk2.isEmpty()){ 21 int leaf1 = getLeafVal(stk1); 22 int leaf2 = getLeafVal(stk2); 23 if(leaf1 != leaf2){ 24 return false; 25 } 26 } 27 28 return stk1.isEmpty() && stk2.isEmpty(); 29 } 30 31 private int getLeafVal(Stack<TreeNode> stk){ 32 while(!stk.isEmpty()){ 33 TreeNode cur = stk.pop(); 34 if(cur.right != null){ 35 stk.push(cur.right); 36 } 37 38 if(cur.left != null){ 39 stk.push(cur.left); 40 } 41 42 if(cur.left == null && cur.right == null){ 43 return cur.val; 44 } 45 } 46 47 return -1; 48 } 49 }
LeetCode 872. Leaf-Similar Trees
原文：https://www.cnblogs.com/Dylan-Java-NYC/p/12131934.html