leetcode

commit 17e0983e0611bf4636f8e1d9e8ad0a0a6d973e7f
parent 83f406f32d8a429653b488d1db007154d9f2649d
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Tue, 10 Jan 2023 19:31:37 +0100

Daily Problem, Iterative solution

Diffstat:
M
Problems/0100.cpp
 | 
29
+++++++++++++++++++++++++++++

1 file changed, 29 insertions(+), 0 deletions(-)
diff --git a/Problems/0100.cpp b/Problems/0100.cpp
@@ -1,3 +1,4 @@
+// Recursive solution
 class Solution {
 public:
   bool isSameTree(TreeNode *p, TreeNode *q) {
@@ -7,3 +8,31 @@ public:
            isSameTree(p->right, q->right);
   }
 };
+
+// Iterative solution
+class Solution {
+public:
+  bool isSameTree(TreeNode *p, TreeNode *q) {
+    if (!p && !q) return true;
+    if (!p || !q) return false;
+    queue<pair<TreeNode *, TreeNode *>> qu;
+    qu.push({p, q});
+    while (!qu.empty()) {
+      auto [p, q] = qu.front();
+      qu.pop();
+      if (p->val != q->val) return false;
+
+      if (p->left && q->left)
+        qu.push({p->left, q->left});
+      else if (p->left || q->left)
+        return false;
+
+      if (p->right && q->right)
+        qu.push({p->right, q->right});
+      else if (p->right || q->right)
+        return false;
+    }
+
+    return true;
+  }
+};