leetcode及牛客网二叉树相关题、单值二叉树、相同的树、二叉树的前序、中序、后序遍历、另一棵树的子树、二叉树的遍历、 对称二叉树等的介绍

---

前言

leetcode及牛客网二叉树相关题、单值二叉树、相同的树、二叉树的前序、中序、后序遍历、另一棵树的子树、二叉树的遍历、 对称二叉树等的介绍

---

一、单值二叉树

leetcode原题： 单值二叉树

---

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*/
bool isUnivalTree(struct TreeNode* root) {if(root == NULL)return true;if(root->left != NULL && root->left->val != root->val )return false;if(root->right != NULL && root->right->val != root->val)return false;return isUnivalTree(root->left) && isUnivalTree(root->right);
}

• 递归思想：
• 每个节点都分别与它的左子树根节点和右子树根节点比较。
• 若传入的节点为NULL，返回 true。（不违反相同的规则）
• 若左右子树分别不为空并且分别不等于根节点则返回 false。

二、相同的树

leetcode原题：相同的树

---

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*/
bool isSameTree(struct TreeNode* p, struct TreeNode* q) {if(p == NULL && q== NULL){return true;}if(p == NULL && q != NULL || p != NULL && q == NULL){return false;}if(p->val != q->val){return false;}return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}

• 递归思想：
• 两棵树同时按照根节点，左子树，右子树的顺序比较每个节点。
• 若两个树根节点都为NULL，则返回true。
• 若两棵树根节点只有一个为NULL，则返回false。
• 若两棵树根节点的值不相等，则返回false。

三、二叉树的前序遍历

leetcode原题： 二叉树的前序遍历

• 其中returnSize是数组元素的个数。传入的是数组元素个数的指针。
• 要求返回一个数组。

---

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*/
/*** Note: The returned array must be malloced, assume caller calls free().*/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 = (int*)malloc(*returnSize * sizeof(int));int i = 0;preorder(root, a, &i);return a;
}

• 思想：
• 先求出这个树的节点个数，赋值给returnSize。
• 动态申请returnSize个空间，同时定义下标变量。
• 在函数preorder中采用前序遍历，将每个节点的值依次赋值给数组。

四、二叉树的中序遍历

leetcode原题： 二叉树的前序遍历

---

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*/
/*** Note: The returned array must be malloced, assume caller calls free().*/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 = (int*)malloc(*returnSize  * sizeof(int));int i = 0;inorder(root, a, &i);return a;
}

五、二叉树的后序遍历

leetcode原题： 二叉树的中序遍历

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*/
/*** Note: The returned array must be malloced, assume caller calls free().*/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 = (int*)malloc(*returnSize * sizeof(int));int i = 0;postorder(root, a, &i);return a;
}

六、另一棵树的子树

leetcode原题： 另一棵树的子树

---

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*/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(isSameTree(root, subRoot)){return true;}return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
}

• 将原二叉树与给定子树进行比较。
• 若相同返回true。
• 若不同，原二叉树的左子树和右子树分别与给定子树比较。有一个相同则返回true。

七、二叉树的遍历

牛客网原题: 二叉树的遍历

---

#include <stdio.h>
#include <stdlib.h>typedef char BTDataType;
typedef struct BinaryTreeNode
{BTDataType val;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
} BTNode;BTNode* preorder(char* arr, int* pi)
{if(arr[*pi] == '#'){(*pi)++;return NULL;}BTNode* root = (BTNode*)malloc(sizeof(BTNode));root->val = arr[(*pi)++];root->left = preorder(arr, pi);root->right = preorder(arr, pi);return root;
}void Inorder(BTNode* root)
{if(root == NULL)return;Inorder(root->left);printf("%c ", root->val);Inorder(root->right);
}int main() {char arr[100] = {0};scanf("%s", arr);int i = 0;BTNode* root = preorder(arr, &i);Inorder(root);return 0;
}

八、 对称二叉树

leetcode原题： 对称二叉树

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*/bool order(struct TreeNode* lret, struct TreeNode* rret)
{if(lret == NULL && rret == NULL)return true;if(lret == NULL || rret == NULL)return false;if(lret->val != rret->val)return false;return order(lret->left, rret->right) && order(lret->right, rret->left);}bool isSymmetric(struct TreeNode* root) {if(root == NULL)return true;return order(root->left, root->right);}

• 如若传入根节点是空树，则返回true。
• 若不是空树，比较它的左右子树。
• 1. 若左右子树都是空，则返回true。
• 2. 若左右子树只有一个是空，则返回false。
• 然后判断当前两个树节点的val是否相等，若不相等返回false。
• 若相等继续找子树。

---

总结

leetcode及牛客网二叉树相关题、单值二叉树、相同的树、二叉树的前序、中序、后序遍历、另一棵树的子树、二叉树的遍历、 对称二叉树等的介绍