公司的网站 优帮云,广东省建设厅投诉网站首页,网站建设 手机和pc,阿里云 企业 网站目录 一、相同的树 二、单值二叉树 三、对称二叉树 四、树的遍历
前序遍历
中序遍历
后序遍历 五、另一颗树的子树 六、二叉树的遍历 七、翻转二叉树 八、平衡二叉树 一、相同的树
链接#xff1a;100. 相同的树 - 力扣#xff08;LeetCode#xff09; bool isSameTree(…目录 一、相同的树 二、单值二叉树 三、对称二叉树 四、树的遍历
前序遍历
中序遍历
后序遍历 五、另一颗树的子树 六、二叉树的遍历 七、翻转二叉树 八、平衡二叉树 一、相同的树
链接100. 相同的树 - 力扣LeetCode 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);
}
首先考虑比较时节点为空的情况当比较到二者节点都为空时则当前二者节点相同返回true。二者节点只有一个为空时 当前二者节点不相同返回false。然后考虑不为空时判断二者的值是否相等不相等返回false。最后递归调用比较二者当前节点的左子树和右子树都为true则返回true。 二、单值二叉树
链接965. 单值二叉树 - 力扣LeetCode 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);
}
首先判断当前节点是否为空如果为空则返回true。如果当前节点不为空则判断其左右子树的值是否与当前节点的值相同如果不同则返回false。如果左右子树的值都与当前节点的值相同则递归判断左右子树是否为同值二叉树即左右子树的所有节点的值都相同。这个递归过程会一直往下遍历到叶子节点如果所有节点的值都相同则返回true否则返回false。 三、对称二叉树 思路左子树的左节点与右子树的右节点比较左子树的右节点和右子树的左节点比较 bool _isSymmetric(struct TreeNode* leftRoot, struct TreeNode* rightRoot) {if (leftRoot NULL rightRoot NULL)return true;if (leftRoot NULL || rightRoot NULL)return false;if (leftRoot-val ! rightRoot-val)return false;return _isSymmetric(leftRoot-left, rightRoot-right) _isSymmetric(leftRoot-right, rightRoot-left);
}bool isSymmetric(struct TreeNode* root) {return _isSymmetric(root-left, root-right);
} OJ是允许我们额外根据需要创建函数的原函数的参数只有一个不能满足同时判断两个节点的是否相等的要求所以我们创建递归函数_isSymmetric()用来判断左右子树是否对称。 如果左右子树都为空说明对称返回true如果左右子树只有一个为空说明不对称返回false如果左右子树的值不相等说明不对称返回false否则递归判断左子树的左子树和右子树的右子树是否对称以及左子树的右子树和右子树的左子树是否对称如果都对称返回true否则返回false。函数isSymmetric()则是调用_isSymmetric()函数传入根节点的左子树和右子树判断整个二叉树是否对称。 四、树的遍历
前序遍历
链接144. 二叉树的前序遍历 - 力扣LeetCode 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 (int*)malloc(*returnSize * sizeof(int));int i 0;_preorder(root, a, i);return a;
} 题中要求我们将前序遍历的结果存到数组中并输出数组那么我们需要创建一个数组插入数据同时我们也需要数组的大小所以我们增加了 TreeSize函数统计树的节点个数_preorder递归函数将节点插入数组。 preorderTraversal函数中
首先将TreeSize统计的树的大小赋值给returnSize。为指针a开辟数组所需的空间用于存放数组元素。整型变量 i 用于记录数组当前的索引。调用_preorder函数对数组进行插入数据。返回数组a。 _preorder函数中
如果当前节点为空则结束函数。否则将当前节点的值插入数组中每次插入结束后数组的索引值加一。这里索引参数为指针类型用于接收索引 i 的地址这样才能在函数中及时更新索引值。递归调用_preorder函数对当前节点的左节点进行处理。左节点处理后递归调用_preorder函数对当前节点的右节点进行处理。
中序遍历
94. 二叉树的中序遍历 - 力扣LeetCode
int TreeSize(struct TreeNode* root) {return root NULL ? 0 : TreeSize(root-left) TreeSize(root-right) 1;
}
void _inorder(struct TreeNode* root, int* a, int* i) {if (root NULL)return;_inorder(root-left, a, i);a[(*i)] root-val;_inorder(root-right, a, i);
}
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;
}
后序遍历
145. 二叉树的后序遍历 - 力扣LeetCode
int TreeSize(struct TreeNode* root) {return root NULL ? 0 : TreeSize(root-left) TreeSize(root-right) 1;
}
void _postorder(struct TreeNode* root, int* a, int* i) {if (root NULL)return;_postorder(root-left, a, i);_postorder(root-right, a, i);a[(*i)] 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;
}
五、另一颗树的子树
链接572. 另一棵树的子树 - 力扣LeetCode 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);
}
调用 isSameTree 辅助判断子树是否相等
首先考虑比较时节点为空的情况当比较到二者节点都为空时则当前二者节点相同返回true。二者节点只有一个为空时 当前二者节点不相同返回false。然后考虑不为空时判断二者的值是否相等不相等返回false。最后递归调用比较二者当前节点的左子树和右子树都为true则返回true。 isSubtree函数
如果 root 是 NULL那么它不可能包含任何子树函数返回 false。如果 isSameTree(root, subRoot) 返回 true说明在当前的节点上root 和 subRoot 完全相同那么 subRoot 当然是 root 的子树函数返回 true。如果当前节点不匹配那么递归地在 root 的左子树和右子树中查找 subRoot。如果 subRoot 是 root 左子树或右子树的子树函数就返回 true。 六、二叉树的遍历
链接二叉树遍历_牛客题霸_牛客网 (nowcoder.com) 我们需要根据给出的先序(前序)遍历反推出树的样子例如下图我们可以动手试一试 好的如果你已经熟悉如何根据遍历反推二叉树的形状那么试着推出题中的遍历的吧。 注意这道题需要写出主函数并不像力扣提供接口。 首先我需要创建二叉树的结构体和相关函数 #include stdio.h
#include stdlib.h
typedef int BTDataType;
typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;
BTNode* BuyNode(BTDataType x)
{BTNode* node(BTNode*)malloc(sizeof(BTNode));if(nodeNULL){perror(malloc fail);return NULL;}node-datax;node-leftnode-rightNULL;return node;
} 然后进行二叉树的创建 该函数接收两个参数一个是字符串a另一个是指向整型变量i的指针用于记录当前处理到字符串a的哪个位置。当前位置数组元素为 # 表示元素值为空更新数组索引到下一个位置返回NULL当前位置元素不为空则为其开辟空间为树创建新节点更新数组索引到下一个位置。递归调用CreateTree函数分别创建该节点的左右子树。最后返回该节点的指针。 在main函数中 先定义了一个字符数组a用于存储输入的字符串然后调用CreateTree函数创建二叉树将根节点的指针赋值给root最后调用InOrder函数对二叉树进行中序遍历并输出换行符。 BTNode* CreateTree(char* a,int* i)
{if(a[*i]#){(*i);return NULL;}BTNode* rootBuyNode(a[*i]);(*i);root-leftCreateTree(a, i);root-rightCreateTree(a, i);return root;
}
void InOrder(BTNode* root)
{if(rootNULL)return;InOrder(root-left);printf(%c ,root-data);InOrder(root-right);
}
int main() {char a[1000];scanf(%s,a);int i0;BTNode* rootCreateTree(a,i);InOrder(root);printf(\n);return 0;
} 七、翻转二叉树
链接226. 翻转二叉树 - 力扣LeetCode truct TreeNode* invertTree(struct TreeNode* root) {if(rootNULL)return NULL;struct TreeNode* leftinvertTree(root-left);struct TreeNode* rightinvertTree(root-right);root-leftright;root-rightleft;return root;
} 如果当前节点为空则返回NULL.否则递归调用函数对左右子树进行处理递归到二叉树最底部从最底部往上进行翻转。将节点的左节点赋值为右节点右节点赋值为左节点最后返回根节点。
八、平衡二叉树
链接110. 平衡二叉树 - 力扣LeetCode 第一种求出左右子树高度进行判断比较。 height函数用于计算二叉树的高度它采用递归的方式计算左右子树的高度然后返回左右子树高度的较大值加1表示当前节点的高度。 isBalanced函数则是用于判断二叉树是否平衡它首先判断当前节点是否为空如果为空则返回true否则通过 abs 函数计算左右子树的高度差的绝对值如果高度差大于1则返回false否则递归判断左右子树是否平衡。 int height(struct TreeNode* root){if(root NULL)return 0;int leftHeight height(root-left);int rightHeight height(root-right);return leftHeight rightHeight ? leftHeight 1 : rightHeight 1;
}bool isBalanced(struct TreeNode* root) {if (root NULL) {return true;}int leftHeight height(root-left);int rightHeight height(root-right);if (abs(leftHeight - rightHeight) 1) {return false;}return isBalanced(root-left) isBalanced(root-right);
} 第二种与第一种功能方法一样但这种方式更简洁 同样首先写出求树高度的函数但这里使用三目运算符使函数更简洁。fmax返回两个参数中较大的那个。 int maxDepth(struct TreeNode* root){return root ? 1 fmax(maxDepth(root-left) , maxDepth(root-right)) : 0;
}bool isBalanced(struct TreeNode* root){if(root NULL)return true;int left maxDepth(root-left);int right maxDepth(root-right);return abs(left - right) 2 isBalanced(root-left) isBalanced(root-right);
}
