盐城网站建设价位,深圳龙岩技术科技有限公司,贵阳装饰装修公司网站,wordpress万年历插件文章目录 LeetCode965. 单值二叉树LeetCode100. 相同的树LeetCode101. 对称二叉树LeetCode144. 二叉树的前序遍历LeetCode94. 二叉树的中序遍历LeetCode145. 二叉树的后序遍历LeetCode572. 另一棵树的子树 LeetCode965. 单值二叉树
题目
Oj链接
思路 一棵树的所有值都是一个… 文章目录 LeetCode965. 单值二叉树LeetCode100. 相同的树LeetCode101. 对称二叉树LeetCode144. 二叉树的前序遍历LeetCode94. 二叉树的中序遍历LeetCode145. 二叉树的后序遍历LeetCode572. 另一棵树的子树 LeetCode965. 单值二叉树
题目
Oj链接
思路 一棵树的所有值都是一个值, 那么就可以认为每个结点的左右孩子都和该结点的值相等 将一棵树分为根 左子树 右子树, 如果值不相等直接返回 false 先判断根结点的左右孩子是否和根结点的值一样 如果一样,先判断左子树,再判断右子树,最后返回两结果的逻辑与结果如果不一样,直接返回false, 代码实现
bool isUnivalTree(struct TreeNode* root)
{if (root NULL) return true;if (root-left root-val ! root-left-val) //如果左子树存在并且值不等, 返回falsereturn false;if (root-right root-val ! root-right-val) //如果右子树存在并且值不等, 返回falsereturn false;return isUnivalTree(root-left) isUnivalTree(root-right); //左子树为单值 右子树为单值
}LeetCode100. 相同的树
题目
Oj链接
思路 如果两个树都为空, 则两树相等;如果两个树中只有一个是空, 那么两数必然不相等.如果两个数都不为空, 则先判断两树的根结点是否值一样. 若一样, 继续递归调用判断左子树和右子树是否都对应相等;若不一样,直接向上一层返回false 代码实现
bool isSameTree(struct TreeNode* p, struct TreeNode* q)
{if (p NULL q NULL) //如果两个结点都是空, 返回true{return true;}if (p NULL || q NULL) //在两个结点不同时为空的情况下, 有一个为空直接返回false{return false;}//剩余就只有两结点都不为空的情况了if (p-val ! q-val){return false;}return isSameTree(p-left, q-left) isSameTree(p-right, q-right);
}LeetCode101. 对称二叉树
题目
Oj链接
思路 和判断两树是否一样的思路差不多 一个树是对称二叉树的条件就是: 根结点的左右孩子一样左子树的左子树 和 右子树的右子树 一样左子树的右子树 和 右子树的左子树 一样 由此对于左右子树的判断我们可以创建一个递归函数, 类似于判断两树是否一样, 函数参数是两个树 如果两个树都是空, 则两树对称如果两个树中只有一个是空, 则两树不对称如果两个数都不为空, 则判断 左左和右右是否相等, 左右和右左是否相同 代码实现
bool isSymmetricTree(struct TreeNode* q, struct TreeNode* p)
{if (q NULL p NULL)return true;if (q NULL || p NULL)return false;if (q-val ! p-val)return false;return isSymmetricTree(q-left, p-right) isSymmetricTree(q-right, p-left);
}bool isSymmetric(struct TreeNode* root)
{if (root NULL)return true;return isSymmetricTree(root-left, root-right);
}LeetCode144. 二叉树的前序遍历
LeetCode94. 二叉树的中序遍历
LeetCode145. 二叉树的后序遍历
三题类似,这里直接一起贴上来 题目 二叉树的前序遍历。 Oj链接
二叉树中序遍历 。Oj链接
二叉树的后序遍历 。Oj链接
思路 就拿前序遍历来说, 对于普通打印的前序遍历就不多说了, 相关可以看我的文章:链式二叉树
在这里, 主要是理解题目意思, 首先我们来看题目给的接口函数描述
int* preorderTraversal(struct TreeNode* root, int* returnSize);函数需要我们将前序遍历的结果存到一个数组当中, 并且将数组返回, 这就需要我们动态开辟一段空间. int* returnSize表示我们同时要返回二叉树的结点个数, 通过传址调用返回. 获得二叉数结点个数, 并开辟同样元素个数空间的数组空间前序遍历二叉树, 自己创建一个递归函数, 为了方便递归调用来存放数据到数组, 将数组下标传址调用 代码实现
前序遍历
// 二叉树结点个数
int binaryTreeSize(struct TreeNode* root)
{if (root NULL){return 0;}return 1 binaryTreeSize(root-left) binaryTreeSize(root-right);
}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 binaryTreeSize(root);int* a (int*)malloc(sizeof(int) * (*returnSize));int index 0;preOrder(root, a, index);return a;
}中序遍历
int TreeSize(struct TreeNode* root)
{return root NULL ? 0 : 1 TreeSize(root-left) TreeSize(root-right);
}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(sizeof(int) * (*returnSize));int index 0;inOrder(root, a, index);return a;
}后序遍历
int TreeSize(struct TreeNode* root)
{return root NULL ? 0 : 1 TreeSize(root-left) TreeSize(root-right);
}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(sizeof(int) * (*returnSize));int index 0;postOrder(root, a, index);return a;
}LeetCode572. 另一棵树的子树
题目
Oj链接
思路 深度搜索每一个结点, 如果结点与subRoot的根结点相同, 则进行判断以这两个结点为根结点的树是否相同 这里需要用到前面用到的判断两个树是否一样的函数代码. 如果 root 和 subRoot 都为空, 则直接返回 true如果 root 和 subRoot 两个只有有一个为空, 则直接返回 false此时只剩下两者都不为空的情况, 深度搜索判断 root 每个结点是否和 subRoot 的根结点一样 如果一样, 则使用 isSameTree进行判断如果不一样, 继续深度搜索 最后将左右子树的两个结果经过逻辑或得到结果 bool isSameTree(struct TreeNode* p, struct TreeNode* q)
{if (p NULL q NULL) //如果两个结点都是空, 返回true{return true;}if (p NULL || q NULL) //在两个结点不同时为空的情况下, 有一个为空直接返回false{return false;}//剩余就只有两结点都不为空的情况了if (p-val ! q-val){return false;}return isSameTree(p-left, q-left) isSameTree(p-right, q-right);
}// 如果根结点对应的树是subRoot, 则返回true
// 如果不是 寻找左子树有没有
// 寻找右子树有没有
bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot)
{if (root NULL subRoot NULL){return true;}if (root NULL || subRoot NULL){return false;}if (root-val subRoot-val){if (isSameTree(root, subRoot)){return true;}}return isSubtree(root-left, subRoot) || isSubtree(root-right, subRoot);
}
