剑指offer：树的子结构、二叉树的镜像、对称的二叉树

本文主要是介绍剑指offer：树的子结构、二叉树的镜像、对称的二叉树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

剑指offer：树的子结构、二叉树的镜像、对称的二叉树

题目: 树的子结构: 输入两棵二叉树A和B，判断B是不是A的子结构。
  分析：
       1. 查找树A中与树B根节点一样的结点(树的遍历)。
       2. 判断A中以该结点为根节点的子树是不是和B具有一样的结构。 
       
       
  注：在写树的代码的时候，要时刻注意该地址是否可能是nullptr

/*struct TreeNode {int val;          //如果定义的是double类型的时候，不能直接使用==判断 struct TreeNode *left;struct TreeNode *right;TreeNode(int x) :val(x), left(NULL), right(NULL) {}
};*/
class Solution {
public://第一步检查根节点是否存在是要遍历完所有的结点，所以要定义result在最后才return bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2){bool result = false; if (pRoot1 != nullptr && pRoot2 != nullptr){// 按照根左右进行遍历 if (pRoot1->val == pRoot2->val) result = Does_has_B(pRoot1, pRoot2);if (!result) result = HasSubtree(pRoot1->left, pRoot2);if (!result) result = HasSubtree(pRoot1->right, pRoot2);}return result;}
private://第二步，检查是否含有B树，只要其中任何一个结点不相等或者树A没了，就需要return false bool Does_has_B(TreeNode* pRoot1, TreeNode* pRoot2){if (pRoot2 == nullptr) return true;if (pRoot1 == nullptr) return false;if (pRoot1->val != pRoot2->val) return false;return Does_has_B(pRoot1->left, pRoot2->left) && Does_has_B(pRoot1->right, pRoot2->right);}
};

题目：二叉树的镜像：完成一个函数，输入一棵二叉树，该函数输出它的镜像

镜像的意思其实就是，左右子树互换，但是要注意，是要递归互换。

/*struct TreeNode {int val;struct TreeNode *left;struct TreeNode *right;TreeNode(int x) :val(x), left(NULL), right(NULL) {}
};*/
class Solution {
public:void Mirror(TreeNode *pRoot) {if (pRoot == nullptr) return;TreeNode* pTemp = pRoot->left;pRoot->left = pRoot->right;pRoot->right = pTemp;if (pRoot->left != nullptr) Mirror(pRoot->left);if (pRoot->right != nullptr) Mirror(pRoot->right);//当所有的都调整完毕后，return return;}
};

题目: 实现一个函数，判断一颗二叉树是不是对称的。如果一个二叉树和它的镜像相同，则为对称二叉树。
思路：建立先序遍历的镜像形式，先序遍历本身是根左右，现在建立一种新的方式，根右左，但是要注意遍历到nullptr,

这样可以避免错误。

/*struct TreeNode {int val;struct TreeNode *left;struct TreeNode *right;TreeNode(int x) :val(x), left(NULL), right(NULL) {}
};*/
class Solution {
public:bool isSymmetrical(TreeNode* pRoot){return isSymmetrical_private(pRoot, pRoot);}
private:bool isSymmetrical_private(TreeNode* pRoot1, TreeNode* pRoot2){if (pRoot1 == nullptr && pRoot2 == nullptr) return true;if (pRoot1 == nullptr || pRoot2 == nullptr) return false;if (pRoot1->val != pRoot2->val) return false;// 等于将root1先序遍历，将root2对称先序遍历，也就是根右左 return isSymmetrical_private(pRoot1->left, pRoot2->right) && isSymmetrical_private(pRoot1->right, pRoot2->left);}
};

 

这篇关于剑指offer：树的子结构、二叉树的镜像、对称的二叉树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---