aboutsummaryrefslogtreecommitdiff
path: root/leaf_similar_trees.cpp
blob: 319fbbf4965f35aa2c8f5f8b052cc3a8941a7562 (plain)
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
#include "leetcode.h"

class Solution {
public:
  bool leafSimilar(TreeNode *root1, TreeNode *root2) {
    stack<TreeNode *> s1, s2;
    s1.push(root1);
    s2.push(root2);
    while (!s1.empty() && !s2.empty())
      if (dfs(s1) != dfs(s2))
        return false;
    return s1.empty() && s2.empty();
  }

private:
  int dfs(stack<TreeNode *> &s) {
    while (true) {
      TreeNode *node = s.top();
      s.pop();
      if (node->right)
        s.push(node->right);
      if (node->left)
        s.push(node->left);
      if (!node->left && !node->right)
        return node->val;
    }
  }
};