Last active
January 28, 2018 09:32
-
-
Save HongfeiXu/4709f736baaa41b5e0099adc98aa5d27 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // Definition for a binary tree node. | |
| struct TreeNode { | |
| int val; | |
| TreeNode *left; | |
| TreeNode *right; | |
| TreeNode(int x) : val(x), left(nullptr), right(nullptr) { } | |
| }; | |
| // 使用先序遍历将二叉树转化为一个字符序列表示的二叉树 | |
| void treeToSequence(TreeNode* root, string& result) | |
| { | |
| if (root == nullptr) | |
| return; | |
| result.append(to_string(root->val)); | |
| if (root->left != nullptr || root->right != nullptr) | |
| { | |
| result.append("("); | |
| treeToSequence(root->left, result); | |
| result.append(","); | |
| treeToSequence(root->right, result); | |
| result.append(")"); | |
| } | |
| } | |
| /* | |
| Input: 1 1 | |
| / \ / \ | |
| 2 1 1 2 | |
| "1(2,1)" | |
| "1(1,2)" | |
| Input: 1 1 | |
| / \ | |
| 2 2 | |
| "1(2,)" | |
| "1(,2)" | |
| */ | |
| // 拷贝一颗二叉树(DFS) | |
| TreeNode* copyTree(TreeNode* root) | |
| { | |
| if (root == nullptr) | |
| return nullptr; | |
| // 拷贝当前根节点 | |
| TreeNode* p = new TreeNode(root->val); | |
| // 拷贝左子树 | |
| p->left = copyTree(root->left); | |
| // 拷贝右子树 | |
| p->right = copyTree(root->right); | |
| return p; | |
| } | |
| // 拷贝该二叉树的对称树 | |
| TreeNode* copySymmetricTree(TreeNode* root) | |
| { | |
| if (root == nullptr) | |
| return nullptr; | |
| // 拷贝当前根节点 | |
| TreeNode* p = new TreeNode(root->val); | |
| // 拷贝左子树，作为右子树 | |
| p->right = copySymmetricTree(root->left); | |
| // 拷贝右子树，作为左子树 | |
| p->left = copySymmetricTree(root->right); | |
| return p; | |
| } | |
| // 将二叉树转化为与之对称的二叉树 | |
| void symmetricTree(TreeNode* root) | |
| { | |
| if (root == nullptr) | |
| return; | |
| swap(root->left, root->right); | |
| symmetricTree(root->left); | |
| symmetricTree(root->right); | |
| } | |
| // 判断两个二叉树是否相等(DFS) | |
| bool isSame(TreeNode* p, TreeNode* q) | |
| { | |
| if (p == nullptr || q == nullptr) | |
| return p == q; | |
| return (p->val == q->val && isSame(p->left, q->left) && isSame(p->right, q->right)); | |
| } | |
| // 判断两个二叉树是否对称 | |
| bool isSymmetric(TreeNode* l, TreeNode* r) | |
| { | |
| // 若l，r中有空节点，则两者相同返回true，不同返回false | |
| if (l == nullptr || r == nullptr) | |
| return l == r; | |
| // 当前节点相同，且l的左子树等于r的右子树，l的右子树等于r的左子树，则l和r对称 | |
| return (l->val == r->val && isSymmetric(l->left, r->right) && isSymmetric(l->right, r->left)); | |
| } | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment