c/c++开发分享C++实现LeetCode(100.判断相同树)

[leetcode] 100. same tree 判断相同树given two binary trees, write a function to check if they are the sam


[leetcode] 100. same tree 判断相同树

given two binary trees, write a function to check if they are the same or not.

two binary trees are considered the same if they are structurally identical and the nodes have the same value.

example 1:

input:     1         1
    /        /
2   3     2   3

        [1,2,3],   [1,2,3]

output: true

example 2:

input:     1         1
/          
2             2

[1,2],     [1,null,2]

output: false

example 3:

input:     1         1
/        /
2   1     1   2

[1,2,1],   [1,1,2]

output: false

判断两棵树是否相同和之前的判断两棵树是否对称都是一样的原理,利用深度优先搜索 dfs 来递归。代码如下:

解法一:

  class solution {  public:      bool issametree(treenode *p, treenode *q) {          if (!p && !q) return true;          if ((p && !q) || (!p && q) || (p->val != q->val)) return false;          return issametree(p->left, q->left) && issametree(p->right, q->right);      }  };

这道题还有非递归的解法,因为二叉树的四种遍历(层序,先序,中序,后序)均有各自的迭代和递归的写法,这里我们先来看先序的迭代写法,相当于同时遍历两个数,然后每个节点都进行比较,可参见之间那道 binary tree preorder traversal,参见代码如下:

解法二:

  class solution {  public:      bool issametree(treenode* p, treenode* q) {          stack<treenode*> st;          st.push(p); st.push(q);          while (!st.empty()) {              p = st.top(); st.pop();              q = st.top(); st.pop();              if (!p && !q) continue;              if ((p && !q) || (!p && q) || (p->val != q->val)) return false;              st.push(p->right); st.push(q->right);              st.push(p->left); st.push(q->left);          }          return true;      }  };

也可以使用中序遍历的迭代写法,对应之前那道 binary tree inorder traversal,参见代码如下:

解法三:

  class solution {  public:      bool issametree(treenode* p, treenode* q) {          stack<treenode*> st;          while (p || q || !st.empty()) {              while (p || q) {                  if ((p && !q) || (!p && q) || (p->val != q->val)) return false;                  st.push(p); st.push(q);                  p = p->left; q = q->left;              }              p = st.top(); st.pop();              q = st.top(); st.pop();              p = p->right; q = q->right;          }          return true;      }  };

对于后序遍历的迭代写法,貌似无法只是用一个栈来做,因为每次取出栈顶元素后不立马移除,这样使用一个栈的话两棵树结点的位置关系就会错乱,分别使用各自的栈就好了,对应之前那道 binary tree postorder traversal,参见代码如下:

解法四:

  class solution {  public:      bool issametree(treenode* p, treenode* q) {          stack<treenode*> st1, st2;          treenode *head1, *head2;          while (p || q || !st1.empty() || !st2.empty()) {              while (p || q) {                  if ((p && !q) || (!p && q) || (p->val != q->val)) return false;                  st1.push(p); st2.push(q);                  p = p->left; q = q->left;              }              p = st1.top();               q = st2.top();               if ((!p->right || p->right == head1) && (!q->right || q->right == head2)) {                  st1.pop(); st2.pop();                  head1 = p; head2 = q;                  p = nullptr; q = nullptr;              } else {                  p = p->right;                  q = q->right;              }          }          return true;      }  };

对于层序遍历的迭代写法,其实跟先序遍历的迭代写法非常的类似,只不过把栈换成了队列,对应之前那道 binary tree level order traversal,参见代码如下:

解法五:

  class solution {  public:      bool issametree(treenode* p, treenode* q) {          queue<treenode*> que;          que.push(p); que.push(q);          while (!que.empty()) {              p = que.front(); que.pop();              q = que.front(); que.pop();              if (!p && !q) continue;              if ((p && !q) || (!p && q) || (p->val != q->val)) return false;              que.push(p->right); que.push(q->right);              que.push(p->left); que.push(q->left);          }          return true;      }  };

github 同步地址:

 

类似题目:

binary tree preorder traversal

binary tree inorder traversal

binary tree postorder traversal

binary tree level order traversal

参考资料:

https://leetcode.com/problems/same-tree/discuss/32684/my-non-recursive-method

https://leetcode.com/problems/same-tree/discuss/32687/five-line-java-solution-with-recursion

到此这篇关于c++实现leetcode(100.判断相同树)的文章就介绍到这了,更多相关c++实现判断相同树内容请搜索<猴子技术宅>以前的文章或继续浏览下面的相关文章希望大家以后多多支持<猴子技术宅>!

需要了解更多c/c++开发分享C++实现LeetCode(100.判断相同树),都可以关注C/C++技术分享栏目—猴子技术宅(www.ssfiction.com)

本文来自网络收集,不代表猴子技术宅立场,如涉及侵权请点击右边联系管理员删除。

如若转载,请注明出处:https://www.ssfiction.com/c-cyuyankaifa/675072.html

发表评论

邮箱地址不会被公开。 必填项已用*标注