leetcode习题分类汇总-Tree篇

Maximum Depth of Binary Tree-返回二叉树的最大深度

思路:

(1)level order triversal,层级遍历,迭代,BFS

(2)递归,返回左右子树中较大的子树长度,DFS




### Same Tree-判断两个数是否相等

思路:DFS,不断判断左右子树是否相同







### Binary Tree Inorder Traversal-二叉树的中序遍历,迭代

思路:while循环,用栈迭代,左中右加到list里




### Binary Tree Preorder Traversal-二叉树的前序遍历

思路:一样的思路,中左右,只不过迭代的顺序不同,多加练习




### Binary Tree Postorder Traversal-二叉树的后序遍历

思路:把前序遍历颠倒着来,利用linkedlist的addFirst()




### Populating Next Right Pointers in Each Node-完全二叉树连接每个右边的节点

思路:迭代,BFS,设置levelstart/cur 两个指针层级遍历




### Populating Next Right Pointers in Each Node II-任意二叉树连接左右节点

思路:
区别在于:每个节点的next节点可以在横向上找到存在的那个节点,无论是父节点next节点的左或者右孩子,又或者是父节点next的next节点的左或者右节点。因此,这道题目首要是找到右孩子的第一个有效的next链接节点,然后再处理左孩子。然后依次递归处理右孩子,左孩子。这道题目的要求和Populating Next Right Pointers in Each Node是一样的,只是这里的二叉树没要求是完全二叉树。其实在实现Populating Next Right Pointers in Each
Node的时候我们已经兼容了不是完全二叉树的情况,其实也比较好实现,就是在判断队列结点时判断一下他的左右结点是否存在就可以了。
Node。时间复杂度和空间复杂度不变,还是O(n)和O(1)。
这道题本质是树的层序遍历,只是队列改成用结点自带的链表结点来维护。






### Unique Binary Search Trees-给定n返回所有可能的二叉搜索树的数量

思路:主要是问题规约,
对于BST是否Unique,很难判断。最后引入了一个条件以后,立即就清晰了,即
当数组为 1,2,3,4,.. i,.. n时,基于以下原则的BST建树具有唯一性:
以i为根节点的树,其左子树由[0, i-1]构成, 其右子树由[i+1, n]构成。
定义Count[i] 为以[0,i]能产生的Unique Binary Tree的数目,

如果数组为空,毫无疑问,只有一种BST,即空树,
Count[0] =1

如果数组仅有一个元素{1},只有一种BST,单个节点
Count[1] = 1

如果数组有两个元素{1,2}, 那么有如下两种可能
1 2
\ /
2 1
Count[2] = Count[0] Count[1] (1为根的情况)
+ Count[1]
Count[0] (2为根的情况。

再看一遍三个元素的数组,可以发现BST的取值方式如下:
Count[3] = Count[0]Count[2] (1为根的情况)
+ Count[1]
Count[1] (2为根的情况)
+ Count[2]Count[0] (3为根的情况)

所以,由此观察,可以得出Count的递推公式为
Count[i] = ∑ Count[0…k]
[ k+1….i] 0<=k<i-1
问题至此划归为一维动态规划。


动态规划,感觉最重要的是递推式和初始值



### Unique Binary Search Trees II-同上,这次直接返回树了

思路:


这道题是求解所有可行的二叉查找树,从Unique Binary Search Trees中我们已经知道,可行的二叉查找树的数量是相应的卡特兰数,不是一个多项式时间的数量级,所以我们要求解所有的树,
自然是不能多项式时间内完成的了。算法上还是用求解NP问题的方法来求解,也就是N
-Queens
中介绍的在循环中调用递归函数求解子问题。
思路是每次一次选取一个结点为根,然后递归求解左右子树的所有结果,
最后根据左右子树的返回的所有子树,依次选取然后接上(每个左边的子树跟所有右边的子树匹配,
而每个右边的子树也要跟所有的左边子树匹配,总共有左右子树数量的乘积种情况),
构造好之后作为当前树的结果返回。
实现中还是有一些细节的,因为构造树时两边要遍历所有左右的匹配,然后接到根上面。
当然我们也可以像在Unique Binary Search Trees中那样存储所有的子树历史信息,然后进行拼合,虽然可以省一些时间,
但是最终还是逃不过每个结果要一次运算,时间复杂度还是非多项式的,并且要耗费大量的空间,
感觉这样的意义就不是很大了。






### Convert Sorted Array to Binary Search Tree-有序数组转化为二叉搜索树

思路:DFS递归,二分法




### Balanced Binary Tree-判断是否为平衡二叉树

思路:DFS递归,不断比较当前左右子树深度是否<=1




### Symmetric Tree-判断是否对称

思路:DFS递归or迭代,递归代码好写点




### Binary Tree Level Order Traversal-二叉树的层级遍历

思路:设置levellast指针,用queue存储遍历




### Binary Tree Level Order Traversal II-bottom-up的层级遍历

思路:和之前一样,用addfirst()就可以。




### Sum Root to Leaf Numbers-计算路径的和

思路:递归或迭代,DFS传值累加,迭代容器选择queue




### Path Sum-判断路径是否存在和为sum值

思路:同上,DFS传值,不断减去当前值


Path Sum II-返回路径和为sum值的所有组合

思路:同上,只是传值的时候多加个list




### Binary Search Tree Iterator-实现二叉搜索树的迭代

思路:维护一个栈,从根节点开始,每次迭代地将根节点的左孩子压入栈,直到左孩子为空为止。

调用next()方法时,弹出栈顶,如果被弹出的元素拥有右孩子,则以右孩子为根,将其左孩子迭代压栈。

Minimum Depth of Binary Tree-二叉树的最小深度 思路:BFS,维护level,DFS,维护最小值



### Flatten Binary Tree to Linked List-二叉树展开为链表

思路:DFS,中左右遍历




### Binary Tree Right Side View-返回左侧值的列表

思路:还是DFS,发现没什么好说的了…




### Recover Binary Search Tree-恢复一颗有两个元素调换错了的二叉查找树

思路:利用二叉查找树的主要性质,就是中序遍历是有序的性质。那么如果其中有元素被调换了,意味着中序遍历中必然出现违背有序的情况。那么会出现几次呢?有两种情况,如果是中序遍历相邻的两个元素被调换了,很容易想到就只需会出现一次违反情况,只需要把这个两个节点记录下来最后调换值就可以;
如果是不相邻的两个元素被调换了,举个例子很容易可以发现,会发生两次逆序的情况,那么这时候需要调换的元素应该是第一次逆序前面的元素,和第二次逆序后面的元素。比如1234567,1和5调换了,会得到5234167,逆序发生在52和41,我们需要把4和1调过来,那么就是52的第一个元素,41的第二个元素调换即可。
搞清楚了规律就容易实现了,中序遍历寻找逆序情况,调换的第一个元素,永远是第一个逆序的第一个元素,
而调换的第二个元素如果只有一次逆序,则是那一次的后一个,如果有两次逆序则是第二次的后一个。算法只需要一次中序遍历,所以时间复杂度是O(n),空间是栈大小O(logn)。





### Binary Tree Maximum Path Sum

思路:


1) Recursively solve this problem
2) Get largest left sum and right sum
2) Compare to the stored maximum



Validate Binary Search Tree-验证是否为BST


思路:对于每一个子树,限制它的最大,最小值,如果超过则返回false。
对于根节点,最大最小都不限制;
每一层节点,左子树限制最大值小于根,右子树最小值大于根;
但是比较有趣的是,在递归的过程中还得不断带入祖父节点的值。

或者,中序遍历该树,然后扫描一遍看是否递增。





Construct Binary Tree from Inorder and Postorder Traversal-已知中序和后序遍历构造BT

思路:利用中序遍历的左中右和post的左右中,不断切分,map建立索引,dfs可以得出当前节点的左右子树,相当于一次树的遍历,时间N,空间N;



### Construct Binary Tree from Preorder and Inorder Traversal已知前序和中序遍历构造BT

思路:一样吧…利用中序遍历的左中右和pre的中左右,不断切分,map建立索引,dfs可以得出当前节点的左右子树,相当于一次树的遍历,时间N,空间N,这样的题目多练习就好。






总结:关于书主要掌握迭代和递归的DFS,BFS遍历方式,重点了解树的前中后序遍历等基础,适当练习加强即可。










###