Tag name:Tree

[LeetCode Summary] Tree Traversal

02/10/2014 / 1 Comment

写一下树的各种遍历以及用遍历结果建树之类的总结
首先前提是树的数据结构就是像下面这样的,后面所有的解法都不考虑在数据结构上做改变(加指向父节点的指针之类的)

递归的方法是最intuitive和readable的,例如中序遍历就是访问一个节点之前要先访问其左子树,然后访问该节点,然后再访问右子树。
前序和后续也是类似,只要交换访问语句的顺序就可以。递归方法时间复杂度都是O(n),空间复杂度则是递归深度,即树的高度O(h)

非递归方法的话,比较容易想到的是用栈+迭代
非递归前序遍历:
方法1是从Programming Interview Exposed看到的,其思路是:
1 先把根节点进栈
2 当栈不为空时,取顶部节点出栈
2.1 访问该节点
2.2 如果右孩子存在,将右孩子压入栈
2.3 如果左孩子存在,将左孩子压入栈

方法1我一开始没想通它是怎么模拟的递归,因为当我想把他套用到中序的非递归遍历的时候,发现是行不通的。之后分析了一下,由于前序遍历根节点遍历完之后,就不再需要使用了,而上面的方法1正是抓住了这个特点,根节点访问完就出栈
而下面这种方法2也是用栈来完成非递归前序遍历,但方法2稍加修改就可以适用于中序遍历(实际上这个方法就是我写中序遍历的时候想到的)
并且这个方法的思路看起来才最接近递归的过程
1 先访问当前节点,再将当前节点压入栈
2 若当前节点有左孩子,对其左孩子重复第一步,直到左孩子为空
3 从栈中取出前一个访问的节点,将其右孩子设为当前节点

未完待续

[LeetCode] Maximum/Minimum Depth of Binary Tree

01/25/2014 / No Comments

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

先做的maximum,maximum实际上就是树的深度或者层数level, 想的比较直接,节点为空depth为0,否则返回左右子树depth中较大的那个+1

然后是minimum depth了,题是这样的
Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

一拿到感觉是一样的,节点为空返回0,否则返回左右子树中depth较小的那个+1

然后问题来了,像这样一棵树,当有一边的子树为空的时候,由于空节点返回0,那函数就认为下面这棵树的minimum depth 为1,而实际应该是4

                                        0

                                 /

                            1

                        /

                   2

                        \

                            3

所以在发现有一边的子树为空的时候,就应该去找另一边的最小长度,因为这一边是没有叶子节点的。