diff options
Diffstat (limited to 'other/leaf_similar_trees.cpp')
-rw-r--r-- | other/leaf_similar_trees.cpp | 28 |
1 files changed, 28 insertions, 0 deletions
diff --git a/other/leaf_similar_trees.cpp b/other/leaf_similar_trees.cpp new file mode 100644 index 0000000..319fbbf --- /dev/null +++ b/other/leaf_similar_trees.cpp @@ -0,0 +1,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; + } + } +}; |