C++实现判断相同树的功能

本篇内容主要讲解“c++实现判断相同树的功能”，感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷，实用性强。下面就让小编来带大家学习“C++实现判断相同树的功能”吧!

判断相同树

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 同步地址：

https://github.com/grandyang/LeetCode/issues/100 

类似题目：

Binary Tree Preorder Traversal

Binary Tree Inorder Traversal

Binary Tree Postorder Traversal

Binary Tree Level Order Traversal

参考资料：

Https://leetcode.com/problems/same-tree/

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++实现判断相同树的功能”有了更深的了解，不妨来实际操作一番吧！这里是编程网网站，更多相关内容可以进入相关频道进行查询，关注我们，继续学习！