>

LeetCode中二叉树标题总计,二叉树的镜像

- 编辑:金沙国际平台登录 -

LeetCode中二叉树标题总计,二叉树的镜像

题目:操作给定的二叉树,将其变换为源二叉树的镜像。

本文仅为博主个人总结,水平有限,欢迎大神指出不妥处。

如:

 

二叉树的镜像定义:源二叉树         8       /        6   10     /   /     5  7 9 11    镜像二叉树        8       /        10   6     /   /     11 9 7  5

关于二叉树的相关概念可以参见二叉树的百度百科,或binary tree Wiki。

分析:递归的交换左右子树。也可以用栈实现。

二叉树结点类的常见定义为:

解法一:递归

1 /* Definition for a binary tree node. */
2  struct TreeNode 
3  {
4      int val;
5      TreeNode *left;
6      TreeNode *right;
7      TreeNode(int x) : val(x), left(NULL), right(NULL) {}
8 };
 1 /* 2 struct TreeNode { 3     int val; 4     struct TreeNode *left; 5     struct TreeNode *right; 6     TreeNode : 7             val, left, right { 8     } 9 };*/10 class Solution {11 public:12     void Mirror(TreeNode *pRoot) {13         if (pRoot == nullptr) {14             return;15         }16         TreeNode *tmp = pRoot->left;17         pRoot->left = pRoot->right;18         pRoot->right = tmp;19         Mirror(pRoot->left);20         Mirror(pRoot->right);21     }22 };

 

解法二:栈实现

提到二叉树,首先要提到二叉树的四种遍历方式:前序遍历、中序遍历、后续遍历和层次遍历,其中前三种为一类,一般是使用栈(stack)实现,三种遍历方式的区别在于访问根结点的顺序不同;最后一种一般使用队列(queue)实现。这四种遍历是很多题目的基础,要弄懂。

一、前序遍历、中序遍历、后续遍历

1、前序遍历:访问顺序是根结点->左孩子->右孩子。迭代算法实现的主要思想为:先访问根结点,然后若右孩子存在就将其存入栈中,若左孩子存在,则根结点沿左孩子一直到叶结点同时依次访问;到了叶结点时, 去除栈顶结点继续访问,直到栈为空。Binary tree preorder traversal。

2、中序遍历:访问顺序是左孩子->根结点->右结点。迭代算法实现的主要思想为:因为先访问左孩子(从身为叶结点的左孩子开始),所以可以利用栈先进后出的特点,我们先沿着左孩子一直将结点存入栈中,到叶结点时,从栈中取出结点开始访问,然后取当前结点的右孩子接着进行循环,直到root为NULL且栈为空。Binary tree inorder traversal。

3、后序遍历:访问顺序是左孩子->右孩子->根结点。迭代算法实现的主要思想为:最重要的是定义一个指针记录下前一个访问过的,这样可以避免重复访问。有两种思路:一、按照后序遍历访问结点的顺序,将右、左孩子入栈(注意入栈顺序),若到达根结点或当前结点的左、右孩子中已被访问过,则从栈中取出结点访问。二、可以从中序遍历的基础上改进,即不断将左孩子压入栈中,然后若当前结点的右孩子没有被访问过,则转向遍历以当前右孩子为根结点的树,若访问过,则取出栈顶元素访问即可。这两种思路中都要注意对前指针的更新。Binary tree postorder traversal。

二、层次遍历

1、一般是:利用队列先进先出的特点,依次将结点的左、右孩子入队,然后依次出队访问,以此为循环。LeetCode中有关这点为Binary tree level order traversal,不过题中要求按行输出每一行结点的值。这里的关键问题是如何分层。迭代算法的实现有三种:一、定义两个计数器:一个记录本层结点数,一个记录下当前层下一层的结点数,这样遍历完一层后输出,然后转向下一层,并更新结点数。二、只需一个计数器,记录下当前行结点数,使用两层while循环结构,每访问完一个结点,计数器减1,直到该层中所有结点访问;然后访问下一行,并通过size()得到该行的结点数,以此进行循环。三、在每一层的最后向栈中压入NULL当作该行的结束符,这样出队时,每遇到NULL时,就保存这一行中的结点,值得注意的时,只有队列不为空时才压入NULL。

2、题Binary tree level order traversal ii是上一题的延续,变化在于结果的输出:从下到上按行输出每行的结点值。有两种方法,一、用上一题的结果,只是到最后,将最后的结果反转就行;二、主体还是和上一题一样,只是以行为单位保存每行结点时,先存入栈中,利用其先进后出的特点完成反转输出。

3,、题Binary tree Zigzag level order traversal可以说是二叉树层次遍历的延续。我们只要在以行为单位将每行结点值存入最终结果时,遇到偶数行时,将该行的结点值反转以后存入最后结果即可。

4、题Maximum depth of binary tree和The minimum depth of binary tree的迭代法可以看成是层次遍历的延续,求最大深度,到最底层即可,最小深度遇到第一个叶结点所在层即可。对于这两题的递归解法,关键在于理解二叉树深度这一概念。

三、使用前序遍历、中序遍历、后续遍历中的两种构建二叉树

根据三种遍历结点的顺序,我们可以得到只有前序遍历+中序遍历、中序遍历+后续遍历才能实现二叉树的构造,而前序遍历+后续遍历是不能构建二叉树的,因为,没法通过根结点的位置将左右子树分开。这两种方式构造二叉树的思路相同,都是先根据根结点确定左右子树,然后依次找到以每个结点的左右子树,递归实现构造二叉树,值得注意的,下标问题。Construct binary tree from preorder and inorder travesal 、Construct binary tree from inorder and postorder travesal 。

四、求和问题

1、题Sum root to leaf numbers,求得是根结点到所有叶结点所形成的数(根结点为最高位)的和。Binary tree maximum path sum 中起始节点可以是任意节点。Path Sum给定一个数,判断二叉树中是否存在从根到叶节点,使路径上所有结点值的和等于给定值。第一题和第三题可看成是一个递归实现的一个逆过程。这几题的关键在于理解题意(特别是第二题)以后,使用递归调用解题。当然第三题可以利用后续遍历的思想实现迭代解题。

2、题Path Sum II是题Path Sum的延续,本题中要输出所有符合题意的路径。迭代解法也是可以通过后续遍历的思想解决。这里分为将这两题分开说的原因,主要是在Path Sum II的递归解法上。这题的递归解法在后面很多题中都可以得到体现,值得注意。

五、填充问题

题Populating next right pointer in each node和Populating next right pointer in each node ii 是一个类型的,一般解法是利用层次遍历的思想,使用队列,来实现层与层之间的转换。在要求不能使用额外空间时,我们可以利用其提供的next指针来实现。第一题中涉及到的几个二叉树的概念可见博友veli的博客。两题的主要思路是,先保存当前行的下一行中最左端的结点以便于实现层层之间转换。至于第二题中要注意的是要定义一个指针,实现层内的穿针引线。参考递归实现可以明白整个算法的结构。

六、一般二叉树的特殊情况

题Same tree和Symmetric tree 是一般二叉树的特殊情况。第一题判断是否为相同二叉树,可以使用两队列,按照层次遍历的方式,两二叉树的左右孩子的入队顺序相同,判断各种情况下是否符合;第二题判断树是否为对称二叉树,首先要理解对称的概念,是从整体上的对称,也可以使用两个队列实现判断,不过要注意的是入队的顺序。也可以使用一个栈,入栈顺序是,先左左,右右,然后左右,右左,对应的入栈,只需比较栈顶连续两结点是否相等即可。

七、搜索二叉树

首先要明白搜索二叉树的概念,针对一棵二叉树是否为搜索二叉树有题Validate binary search tree ,要紧紧的围绕搜索二叉树的中序遍历是非降序列来解题。有几种方法:一、定义一个指针指向当前结点的前一个结点,利用二叉树中序遍历的思路,将两者的值进行比较,只要前者大于后者就不是搜索二叉树;二、可以将利用中序遍历将二叉树结点值都存入一个数组中,然后遍历数组看是否为非降序型。

题Unique binary search trees 给定数列,判断能构成几种不同的二叉搜索树。关键在弄明白给定数和搜索二叉树种类的关系(卡特兰数)。然后依次可以写出动态规划或递归的解法。Unique binary search trees ii 和Path Sum II的递归解法都是类似的,要深刻体会。

题Recover binary search tree 关键在找到出错的地方,有两种方式,一:可以将结点的值存入数组中,然后排序以后,将值依次赋给对应节点;二:使用中序遍历,找到出错的点,然后交换即可。

其他

Balanced binary tree,这题关键在理解平衡二叉树的概念:任何结点为根结点的左、右子树的深度差不超过1(最大深度差)。

二叉树中两个结点最近的公共祖先汇总中讲解了搜索二叉树、一般二叉树带指向父结点的指针和一般二叉树的最近公共祖先。三者依次,利用二叉搜索树的根结点大于左孩子小于右孩子的特点;将二叉树转变为链表类型;当给定两结点值在某一节点的左右子树中时,为最近的公共祖先的思想。

 

本文由编程发布,转载请注明来源:LeetCode中二叉树标题总计,二叉树的镜像