《数据结构与算法》二叉树基础OJ练习

二叉树的基础知识详见：《数据结构与算法》二叉树-CSDN博客

1 单值二叉树

思路

我们把树分成当前树（用根和左孩子还有右孩子进行比较，如果左孩子或者右孩子为空那就不比了，如果左右孩子或者其中一个存在就比较，相等就是单值二叉树）和左右子树，当前树比较完之后，没有违反规则就再去递归左子树和右子树，每棵树都跟它的左右子树进行比较。每个根都和孩子是相等的，那么整棵树都是相等的，只要有一个不相等那就不是单值二叉树了。

代码实现

bool isUnivalTree(struct TreeNode* root) {if(root == NULL)return true;if(root->left && root->left->val != root->val)return false;if(root->right && root->right->val != root->val)return false;return isUnivalTree(root->left) && isUnivalTree(root->right);
}

2 检查两棵树是否相同

思路

将p和q的根、左子树和右子树分别进行比较，一有不一样的地方立刻返回空。

代码实现

bool isSameTree(struct TreeNode* p, struct TreeNode* q) {if(p == NULL && q == NULL)return true;if(p == NULL || q == NULL)return false;if(p->val != q->val)return false;return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}

3 对称二叉树

思路

根和根比较，左子树和右子树比较，右子树和左子树比较，和检查两棵树是否相同类似。

代码实现

bool _isSymmetric(struct TreeNode* root1, struct TreeNode* root2){  if(root1 == NULL && root2 == NULL)return true;if(root1 == NULL || root2 == NULL)return false;if(root1->val != root2->val)return false;return _isSymmetric(root1->left,root2->right) && _isSymmetric(root1->right, root2->left);
}bool isSymmetric(struct TreeNode* root) {return _isSymmetric(root->left, root->right);
}

4 二叉树的前序遍历

思路

先计算二叉树中的节点个数，再开辟相应大小的数组来存放前序遍历的值。

代码实现

错误代码

int TreeSize(struct TreeNode* root){return root == NULL ? 0 :TreeSize(root->left) + TreeSize(root->right) + 1;
}void preorder(struct TreeNode* root, int* a, int i){if(root == NULL)return;a[i++] = root->val;preorder(root->left, a, i); preorder(root->right, a, i);
}int* preorderTraversal(struct TreeNode* root, int* returnSize) {*returnSize = TreeSize(root);int* a = malloc(sizeof(int)*(*returnSize));int i = 0;preorder(root, a, i);return a;
}

这个时候preorder中的i，在执行完preorder(root->left, a, i)语句之后，再去执行preorder(root->right, a, i)语句的时候i仍然是1，没有改变，就导致在遍历右子树存值进数组的时候出现错误。我们应该传i的地址，这样才能(*pi)++去真正改变i的值。

正确代码

int TreeSize(struct TreeNode* root){return root == NULL ? 0 :TreeSize(root->left) + TreeSize(root->right) + 1;
}void preorder(struct TreeNode* root, int* a, int* pi){if(root == NULL)return;a[(*pi)++] = root->val;preorder(root->left, a, pi); preorder(root->right, a, pi);
}int* preorderTraversal(struct TreeNode* root, int* returnSize) {*returnSize = TreeSize(root);int* a = malloc(sizeof(int)*(*returnSize));int i = 0;preorder(root, a, &i);return a;
}

5 二叉树的中序遍历

思路

与二叉树的前序遍历思路类似。

代码实现

int TreeSize(struct TreeNode* root){return root == NULL ? 0 :TreeSize(root->left) + TreeSize(root->right) + 1;
}void inorder(struct TreeNode* root, int* a, int* pi){if(root == NULL)return;inorder(root->left, a, pi); a[(*pi)++] = root->val;inorder(root->right, a, pi);
}int* inorderTraversal(struct TreeNode* root, int* returnSize) {*returnSize = TreeSize(root);int* a = malloc(sizeof(int)*(*returnSize));int i = 0;inorder(root, a, &i);return a;
}

6 二叉树的后序遍历

思路

与二叉树的前序遍历思路类似。

代码实现

int TreeSize(struct TreeNode* root){return root == NULL ? 0 :TreeSize(root->left) + TreeSize(root->right) + 1;
}void postorder(struct TreeNode* root, int* a, int* pi){if(root == NULL)return;postorder(root->left, a, pi); postorder(root->right, a, pi);a[(*pi)++] = root->val;
}int* postorderTraversal(struct TreeNode* root, int* returnSize) {*returnSize = TreeSize(root);int* a = malloc(sizeof(int)*(*returnSize));int i = 0;postorder(root, a, &i);return a;
}

7 另一棵树的子树

思路

在root树中找到子树的根与subRoot树的根相同的子树，再进行树是否相同的比较（复用检查两棵树是否相同的代码）。

代码实现

bool isSameTree(struct TreeNode* p, struct TreeNode* q) {if(p == NULL && q == NULL)return true;if(p == NULL || q == NULL)return false;if(p->val != q->val)return false;return isSameTree(p->left, q->left) && isSameTree(p->right, q->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);
}