首页 > 代码库 > [C++]LeetCode: 89 Same Tree
[C++]LeetCode: 89 Same Tree
Given two binary trees, write a function to check if they are equal or not.
Two binary trees are considered equal if they are structurally identical and the nodes have the same value.
Answer 1: DFS递归法
思路:先判断根结点是否相等,再递归判断左子树和右子树。
Attention:
1. 注意判断特殊情况,如果两棵树都为空树,返回True. 如果只有一颗空数,另外一颗非空,返回False. 只有在判断非空的请款下,才能判断其值或者push等。
if(p == NULL || q == NULL) return p == q;
复杂度:O(N),N为树的节点个数。
AC Code:
/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: bool isSameTree(TreeNode *p, TreeNode *q) { if(p == NULL && q == NULL) { return true; } else if(p != NULL && q != NULL) { return (p->val == q->val) && isSameTree(p->left, q->left) && isSameTree(p->right, q->right); } else return false; } };
Answer 2: 非递归法
思路:层序遍历树,我们建立两个队列用于保存树的层序节点。每次从队列中取出一个元素,如果他们的值相等,则继续遍历它的子结点。在判断两颗树的子结点是否相等,只有两种情况相等,要不节点同时非空且值相等,要不同时为空。如果一个为空,另外一个非空,两棵树不一样。
Attention:
1. 要保证结构上树也一样,必须在存储子结点前,先判断节点的位置是否一致。
//需要检查是否该节点的左右孩子都在,如果不一致的话(一个没有子结点,一个有子结点),说明不相等 if(tmpP->left && tmpQ->left) { TreeP.push(tmpP->left); TreeQ.push(tmpQ->left); } else if(tmpP->left || tmpQ->left) return false;
二叉树的存储形式是
1 / 2 3 / 4 5The above binary tree is serialized as
"{1,2,3,#,#,4,#,#,5}"
.#代表一条路径的终点,表示此处没有节点,只用来占位(表征二叉树的结构),并不代表一个节点。在处理树的问题时,就按照树的结构去想问题。不需要考虑#的影响。if(root->left) 表示判断根结点是否有左节点,有就为ture, 没有就false. 不会因为此处存储为#,就变为true.
2. 我们只能将非空节点放进队列中,所以需要先判断节点是否非空。
if(p) TreeP.push(p); if(q) TreeQ.push(q);3. 如果最后一个队列为空,另一个队列非空,则说明树不相等,要注意做最后的一个判断。
if(TreeP.empty() && TreeQ.empty()) return true; else return false;AC Code:
/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: bool isSameTree(TreeNode *p, TreeNode *q) { //二叉树不存在的节点会存为#(空出位置来)tmpP->left = #。直到最后一个叶结点,之后就没有存储了, tmpP->left将变成空 if(p == NULL || q == NULL) return p == q; queue<TreeNode*> TreeP; queue<TreeNode*> TreeQ; if(p) TreeP.push(p); if(q) TreeQ.push(q); while(!TreeP.empty() && !TreeQ.empty()) { TreeNode* tmpP = TreeP.front(); TreeP.pop(); TreeNode* tmpQ = TreeQ.front(); TreeQ.pop(); if(tmpP->val == tmpQ->val) { //需要检查是否该节点的左右孩子都在,如果不一致的话(一个没有子结点,一个有子结点),说明不相等 if(tmpP->left && tmpQ->left) { TreeP.push(tmpP->left); TreeQ.push(tmpQ->left); } else if(tmpP->left || tmpQ->left) return false; if(tmpP->right && tmpQ->right) { TreeP.push(tmpP->right); TreeQ.push(tmpQ->right); } else if(tmpP->right || tmpQ->right) return false; } else return false; } if(TreeP.empty() && TreeQ.empty()) return true; else return false; } };
[C++]LeetCode: 89 Same Tree