1+ // Runtime: 0 ms, faster than 100.00% of C++ online submissions for Leaf-Similar Trees.
2+ // Memory Usage: 13.3 MB, less than 88.89% of C++ online submissions for Leaf-Similar Trees.
3+
4+ /* *
5+ * Definition for a binary tree node.
6+ * struct TreeNode {
7+ * int val;
8+ * TreeNode *left;
9+ * TreeNode *right;
10+ * TreeNode(int x) : val(x), left(NULL), right(NULL) {}
11+ * };
12+ */
13+ class Solution
14+ {
15+ public:
16+ bool leafSimilar (TreeNode* root1, TreeNode* root2)
17+ {
18+ vector<int > leaf1;
19+ vector<int > leaf2;
20+
21+ traversal (leaf1, root1);
22+ traversal (leaf2, root2);
23+
24+ if (leaf1.size () != leaf2.size ())
25+ {
26+ return false ;
27+ }
28+ else
29+ {
30+ for (int i =0 ; i < leaf1.size (); ++i)
31+ {
32+ if (leaf1[i] != leaf2[i])
33+ {
34+ return false ;
35+ }
36+ }
37+ return true ;
38+ }
39+ }
40+ private:
41+ void traversal (vector<int >& res, TreeNode* root)
42+ {
43+ stack<TreeNode*> memo;
44+
45+ while (!memo.empty () || root)
46+ {
47+ while (root)
48+ {
49+ if (root->left ==nullptr && root->right ==nullptr )
50+ {
51+ res.push_back (root->val );
52+ }
53+ memo.push (root);
54+ root = root->left ;
55+ }
56+ if (!memo.empty ())
57+ {
58+ root = memo.top ();
59+ memo.pop ();
60+
61+ root = root->right ;
62+ }
63+ }
64+ }
65+ };