class Solution { public: TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { if(root == NULL || root == p || root == q) return root; TreeNode* l = lowestCommonAncestor(root->left, p, q); TreeNode* r = lowestCommonAncestor(root->rig…

2018年4月23日 0条评论 13点热度 阅读全文

class Solution { public: TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { if(root == NULL || root == p || root == q) return root; TreeNode* l = lowestCommonAncestor(root->left, p, q); TreeNode* r = lowestCommonAncestor(root->rig…

2018年4月23日 0条评论 13点热度 阅读全文

题目描述:反转二叉树,如下图: ![这里写图片描述](https://img-blog.csdn.net/20180330182536546?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzIwMTc3MzI3/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70) **解题思路:**理解一下题目,其实要做的就是递归的将二叉树的左右子树进行交换,递归实现非常简单。 C++实现如下: class …

2018年3月30日 0条评论 15点热度 阅读全文

题目描述:反转二叉树,如下图: ![这里写图片描述](https://img-blog.csdn.net/20180330182536546?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzIwMTc3MzI3/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70) **解题思路:**理解一下题目,其实要做的就是递归的将二叉树的左右子树进行交换,递归实现非常简单。 C++实现如下: class …

2018年3月30日 0条评论 10点热度 阅读全文

题目描述:   如果把二叉树看作图,父子结点间的连线是双向的,我们姑且定义“距离”为两个结点之间边的个数,如下图所示,相距最远的两个结点是A和B,距离为6。写程序实现二叉树中相距最远的两个结点之间的距离。 思路分析:   计算一棵二叉树的最大距离有两种情况,第一种是路径经过左子树的最深结点,通过根节点,再到右子树的最深结点,那么距离就是左右子树的深度和;另一种情况是,路径不穿过根节点,只在左子树或者右子树,那么距离就是左子树和右子树距离的最大值。 C++代码实现: struct TreeNode{ int Lmax…

2017年10月20日 0条评论 19点热度 阅读全文

题目描述:   如果把二叉树看作图,父子结点间的连线是双向的,我们姑且定义“距离”为两个结点之间边的个数,如下图所示,相距最远的两个结点是A和B,距离为6。写程序实现二叉树中相距最远的两个结点之间的距离。 思路分析:   计算一棵二叉树的最大距离有两种情况,第一种是路径经过左子树的最深结点,通过根节点,再到右子树的最深结点,那么距离就是左右子树的深度和;另一种情况是,路径不穿过根节点,只在左子树或者右子树,那么距离就是左子树和右子树距离的最大值。 C++代码实现: struct TreeNode{ int Lmax…

2017年10月20日 0条评论 40点热度 阅读全文

  二叉树的宽度是指二叉树各层结点个数的最大值。求二叉树的宽度可以依据与二叉树的层次遍历,我们知道,二叉树的层次遍历借助于deque实现,每次打印当前结点后将其左子树右子树入队,此时队列中既包含当前层的结点,也包含下一层的结点,若我们将当前层的结点全部出队,剩余的就是下一层的结点个数。所以,我们可以使用maxWidth来表示最大宽度,若下一层的结点个数大于maxWidth,则更新maxWidth,最终队列为空,得到的maxWidth即为二叉树的宽度。 以下是C++实现的源代码: //求二叉树的宽度 int Widt…

2017年10月19日 0条评论 11点热度 阅读全文

  二叉树的宽度是指二叉树各层结点个数的最大值。求二叉树的宽度可以依据与二叉树的层次遍历,我们知道,二叉树的层次遍历借助于deque实现,每次打印当前结点后将其左子树右子树入队,此时队列中既包含当前层的结点,也包含下一层的结点,若我们将当前层的结点全部出队,剩余的就是下一层的结点个数。所以,我们可以使用maxWidth来表示最大宽度,若下一层的结点个数大于maxWidth,则更新maxWidth,最终队列为空,得到的maxWidth即为二叉树的宽度。 以下是C++实现的源代码: //求二叉树的宽度 int Widt…

2017年10月19日 0条评论 13点热度 阅读全文

  满二叉树的定义如下:一个深度为k,结点个数为2^k-1的二叉树为满二叉树;完全二叉树的定义如下:二叉树只有最下层和次下层存在叶子结点,并且最下层的叶子结点只能集中在该层最左边的位置,显然,满二叉树也是完全二叉树。   那该如何判断一棵二叉树是否为完全二叉树呢?任意一棵二叉树,我们可以将它补成满二叉树,这样,没有结点的地方都为null。在层次遍历的时候,如果是完全二叉树,这些null结点一定在层次遍历的末尾,所以,当遍历至null的时候,二叉树的遍历已经完成;但是,如果这棵树不是完全二叉树,当我们遍历到null的…

2017年10月19日 0条评论 15点热度 阅读全文

  满二叉树的定义如下:一个深度为k,结点个数为2^k-1的二叉树为满二叉树;完全二叉树的定义如下:二叉树只有最下层和次下层存在叶子结点,并且最下层的叶子结点只能集中在该层最左边的位置,显然,满二叉树也是完全二叉树。   那该如何判断一棵二叉树是否为完全二叉树呢?任意一棵二叉树,我们可以将它补成满二叉树,这样,没有结点的地方都为null。在层次遍历的时候,如果是完全二叉树,这些null结点一定在层次遍历的末尾,所以,当遍历至null的时候,二叉树的遍历已经完成;但是,如果这棵树不是完全二叉树,当我们遍历到null的…

2017年10月19日 0条评论 20点热度 阅读全文