题解 | #树的子结构#
树的子结构
http://www.nowcoder.com/practice/6e196c44c7004d15b1610b9afca8bd88
描述
输入两棵二叉树A,B,判断B是不是A的子结构。(ps:我们约定空树不是任意一个树的子结构)
基本思路
按照树 A 中每个节点的遍历顺序比较当前节点和 B 的根节点是否相同,如果相同就按照 B 的结构遍历他们的每个节点。
例子是题目所给的样例:
A : {8,8,#,9,#,2,#,5} B : {8,9,#,2}
1.两个节点都是 8 ,根节点相同,开始遍历其他节点。
2. 第二个节点不相同函数结束
3. 继续比较 A 中节点和 B 的根节点,再次发现相同
4. 按照 B 的顺序遍历所有节点发现 B 是 A 的子树
复杂度分析
在最坏情况下, 把 A 遍历了一遍,并且对于每个根节点都把 B 遍历了一遍,假设 A 和 B 分别有 m, n 个节点, 所以最坏的时间复杂度是 O(m * n)。
算法实现
详尽的注释都写在 c++ 版本的代码中。
递归方式
// c++ class Solution { public: // 函数返回子树 p1 和 p2 是否有相同结构 bool isSub(TreeNode* p1, TreeNode* p2) { if (!p2) return true; else if (!p1) return false; // p1 和 p2 的根节点相同并且 p1 和 p2 的左子树和右子树分别相同 return p1->val == p2->val && isSub(p1->left, p2->left) && isSub(p1->right, p2->right); } // 函数返回树 p1 中是否有子树 p2 bool HasSubtree(TreeNode* p1, TreeNode* p2) { if (!p1 || !p2) return false; // p1 和 p2 结构相同,或者 p1 左子树或者右子树中有 p2 return isSub(p1, p2) || HasSubtree(p1->left, p2) || HasSubtree(p1->right, p2); } };
# python3 class Solution: def isSub(self, p1, p2): if not p2: return True if not p1: return False return p1.val == p2.val and self.isSub(p1.left, p2.left) and self.isSub(p1.right, p2.right) def HasSubtree(self, p1, p2): if not p1 or not p2: return False return self.isSub(p1, p2) or self.HasSubtree(p1.left, p2) or self.HasSubtree(p1.right, p2)
非递归方式
// c++ class Solution { public: bool isSub(TreeNode* p1, TreeNode* p2) { if (!p2) return true; if (!p1) return false; return p1->val == p2->val && isSub(p1->left, p2->left) && isSub(p1->right, p2->right); } // 中序遍历的方式遍历树 p1 bool HasSubtree(TreeNode* p1, TreeNode* p2) { if (!p2) return false; stack<TreeNode*> st; while (p1 || !st.empty()) { while (p1) { if (p1->val == p2->val && isSub(p1, p2)) return true; st.push(p1); p1 = p1->left; } TreeNode* t = st.top(); st.pop(); p1 = t->right; } return false; }