门户网站怎么做优化,朝阳市做网站的公司,网站建设中一览二栏什么意思,中国网库网站介绍这个系列的文章将带大家一起刷题#xff0c;并且总结思路
温馨提示#xff1a;本篇文章里的练习题仅适合刚学完二叉树的小白使用 相同的树 思路
情况分析#xff1a;第一种情况#xff1a;两棵树都为空 → 返回true 第二种情况并且总结思路
温馨提示本篇文章里的练习题仅适合刚学完二叉树的小白使用 相同的树 思路
情况分析第一种情况两棵树都为空 → 返回true 第二种情况一棵树为空另一棵树不为空→ 返回false 第三种情况 两棵树都不为空 → 判断每个节点的数值是否相同
源代码
bool isSameTree(struct TreeNode* p, struct TreeNode* q) { if(q NULL p NULL) return true; if(q NULL || p NULL) return false; if(p-val ! q-val) return false; return isSameTree(q-left, p-left) isSameTree(q-right, p-right);
}
变式题 思路上与第一题的一模一样但不同的是这次需要遍历树的左右叶子并且判断是否处在相反的位置
思路
情况分析第一种情况两棵树都为空 → 返回true 第二种情况一棵树为空另一棵树不为空→ 返回false 第三种情况 两棵树都不为空 → 判断每个节点的数值是否相同
源代码
bool _isSymmetric(struct TreeNode* p, struct TreeNode* q) { if(q NULL p NULL) return true; if(q NULL || p NULL) return false; if( q-val ! p-val) return false; return _isSymmetric(q-left, p-right) _isSymmetric(q-right, p-left); }
bool isSymmetric(struct TreeNode* root) { return _isSymmetric(root-left, root-right);
}
另一棵树的子树 思路 另一棵树的子树 第二种情况 root为空时 则没有子树可与还在等待比较的树进行比较因此返回false
第三种情况root不为空则先比较根节点的值是否相等比较完根的节点后再比较叶子的节点的数值是否相等
源代码
bool isSameTree(struct TreeNode* p, struct TreeNode* q) { if(q NULL p NULL) return true; if(q NULL || p NULL) return false; if(p-val ! q-val) return false; return isSameTree(q-left, p-left) isSameTree(q-right, p-right);
} bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot){ if(root NULL) return false; if(root-val subRoot-val isSameTree(root, subRoot)) return true; return isSubtree(root-left, subRoot) || isSubtree(root-right,subRoot);
}
刷题总结
从本篇文章中的三道习题以及我自己的刷题中发现类似于这种类型的题不管考察的是否为二叉树也好还是链表也好我们都需要考虑它是否为空以及为空时是否可取
好的本篇文章就先带大家刷到这里还请各位观众老爷赏个三连谢谢啦
