汉诺塔问题

这个问题我在廖雪峰的网站上也解答过了,这里再来回顾下如何在python中使用递归函数解答该问题。
问题:请编写move(n, a, b, c)函数,它接收参数n,表示3个柱子A、B、C中第1个柱子A的盘子数量,然后打印出把所有盘子从A借助B移动到C的方法。助理的A,B,C代表三个柱子的名字。

#调用方法:
move(3, 'A', 'B', 'C')
# 期待输出:
# A --> C
# A --> B
# C --> B
# A --> C
# B --> A
# B --> C
# A --> C

解题思路
(1) 一定要理解递归的内涵。当你定义好一个递归函数的时候,你一定要明白这个递归函数的作用。例如在这个问题中move(n,a,b,c)就代表着有n个盘需要从a通过b的帮助来移动到c;而且注意这里的第2,3,4个参数是变量,代表着柱子的名字。move(5,m,n,k)就代表有3个柱子分别叫做m,n,k,我需要把5个盘子从m通过n移动到k

(2) 这里可以把顶部的n-1个盘子看成一个整体,这样这个问题就变成只要解决2个盘子的问题了,步骤自然是只要3步即可。由于我们把其中的n-1个盘子看成了整体,所以每次要对这n-1个盘子进行操作的时候就要使用递归函数。因为n-1个盘子不是随便就能移动的。这就是使用递归函数的时机

(3) 有人可能会问为什么不把底部的n-1个盘子看成一个整体来移动?这是因为汉诺塔的规则限制,小盘子必须放在大盘子上面。如果你把底部n-1个盘子看成整体来递归操作,会发现违反这种规则的情况,所以是不建议这么做的

代码如下:

__author__ = 'Kaiming'


def move(n, a, b, c):

    #move(n,a,b,c)表示把n个盘子通过b从a移动到c
    #把这个函数理解成2个盘子的移动

    #出递归条件
    if n == 0:
        return None


    #顶部的n-1个盘子从a移动到b
    move(n-1,a,c,b)

    #最后一个盘子移动到c
    print(a,'->',c)


    #顶部的n-1个盘子从b移动到c
    move(n-1,b,a,c)

    return None
move(3, 'A', 'B', 'C')

二叉树上的应用

前几天在亚马逊的笔试题中遇到了一道关于二叉树求最短路径的题目,也可以用递归函数来解答,不过亚马逊只提供了JAVA和C++,现在我们用python来解答下这一道题。

题目:
一颗二叉树,每个节点都有自己的值,在二叉树上找到一条路径(根节点到某个叶子节点之间的路线就是路径)上所有节点的值要最小,输出最小的值是多少!这里的最短路径不是按跳数来,而是按节点值的和来,不要搞错了!

示例:
一行的开头如果输入为0,表示结束输入,空节点用null表示

输入1:
    5
2       3
0
输出1:
7
输入2(记不清了,自己大致编个):
                                                      1
                                        2                        18
                                3             5            null       2
                         100    1    null    8     null             null
                         0
 输出2 :(1+2+3=7这个值最小,是最短路径)
 7           

代码: