[Leetcode] Same Tree

1最容易想到的递归调用

 1 bool isSameTree(TreeNode *r1, TreeNode *r2)
 2 {
 3     if(r1 == NULL && r2 == NULL) return true; //终止条件
 4     if(r1 == NULL || r2 == NULL) return false;//减枝，我觉得也是终止条件
 5 
 6     if(r1->val == r2->val
 7         && isSameTree(r1->left, r2->left)
 8         && isSameTree(r1->right, r2->right)) //递归，三方合并
 9         return true;
10     return false;
11 }

2 迭代，受下面前序方法的启发

前序：

 1 class Solution {
 2     public:
 3         vector<int> preorderTraversal(TreeNode *root) {
 4             vector<int> result;
 5             const TreeNode *p;
 6             stack<const TreeNode *> s;
 7             p = root;
 8             if (p != nullptr) s.push(p);
 9             while (!s.empty()) {
10                 p = s.top();
11                 s.pop();
12                 result.push_back(p->val);
13                 if (p->right != nullptr) s.push(p->right);
14                 if (p->left != nullptr) s.push(p->left);
15             }
16             return result;
17         }
18 };

迭代：

 1 class Solution {
 2     public:
 3         bool isSameTree(TreeNode *r1, TreeNode* r2) {
 4 
 5             if(r1 == NULL && r2 == NULL) return true;
 6             if(r1 == NULL || r2 == NULL) return false;
 7 
 8             stack<TreeNode*> stack;
 9             stack.push(r1);
10             stack.push(r2);
11 
12             TreeNode *p1;
13             TreeNode *p2;
14 
15             while(!stack.empty())
16             {
17                 p1 = stack.top();
18                 stack.pop();
19                 p2 = stack.top();
20                 stack.pop();
21 
22                 if(p1 == NULL && p2 == NULL) continue;//都为空时无法调用p1->right，p1->left
23                 if(p1 == NULL || p2 == NULL) return false;
24                 if(p1->val != p2->val) return false;
25 
26                 stack.push(p1->right);
27                 stack.push(p2->right);
28 
29                 stack.push(p1->left);
30                 stack.push(p2->left);
31                 
32             }
33 
34             return true;
35         }
36 
37 };