|
看着朱元璋的坟头，我深深感慨，死亡是一种解脱。然而人既然活着，有些事不得不去做。明知道转头即空，却留恋不愿放手。明知道前方除了黑暗还有迷茫，却不肯回头。明知道爱的本质是欲望，却不死心。 这几天复习了一些旧东西，同时学习了新东西。这里感谢就良同学的专栏，他对递归的解释让我豁然开朗。 递归（recursion）就是子程序（或函数）直接调用自己或通过一系列调用语句间接调用自己。该执行过程要求每一次节点中断调用其他方法，必须记录下该中断节点的环境信息，作用是为了调用结束返回结果之后原程序能够从上次中断位置起继续执行，在计算机中，通过一个栈结构来实现该效果(栈:先进后出)： 作者：就良同学 这里的解释和寄存器（register）的作用很像，一个微型处理系统如何同时调用多个进程，靠的就是寄存器保留了线程被中断时未完成的操作以及现场的数据。当中断响应结束的时候，再从控制寄存器和数据寄存器中取值，对数据继续进行中断的操作。有趣的是，这里的递归一次又一次不厌其烦的中断，一般微型处理系统可吃不消这么折腾，太复杂了。 下面以斐波拉契数列的递归实现来简要说明: 这里在函数自己调用自己的时候并没有什么数据要保存，只有前两个数相加的操作被记录下来了，需要等待被调用的函数的返回值。对于有数据需要保存的时候，有时候需要借助函数外部数组来记录数据，因为函数调用结束，内部的数据随即消失。只能画成下面的样子了，大家凑合着看，可以看见空间复杂度是很大的，斐波拉契数列的第八个数21，需要有21个1相加，从二叉树的角度看，深度是6。验证了就亮同学说的，方便了程序员，难为了机器。 另一个思路就是正向求解，非常简单，1，1，2，3，5，8，13，21... 这里的思路来源于数组排序的双指针操作，c由a 和b产生，然后再把b的值给a，c的值给b，循环往复。 下面来说链表，这个问题我也是想了很久，因为python里面每个节点定义为类，地址和数据都是类下面的成员，我一时不太明白。 如下图所示，每个成员next指向下一个类的名称，这样就把所有的类串起来了，变成了链表，每个类都是一个node。具体操作的时候，还需要一个临时的可以移动的指针，来实现链表的增减和修改。 二叉树深度的求解 先解释一下四种遍历方法， 中序遍历就是从最左边开始，把每个节点垂直投影到同一直线上，然后从左往右读值就可以了 后序遍历就像是剪葡萄，我们要把一串葡萄剪成一颗一颗的。
在这之后，我尝试用非递归的办法求解二叉树的深度，采用先序遍历的方法，使用了两个栈，一个压入根节点右边和左边的子节点，一个压入子节点对应的深度，遍历完之后求出最大的深度。 # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def maxDepth(self, root: TreeNode) -> int: #遍历深度 deep = 0 #所有遍历的值 res = [] #所有遍历的值对应的深度 deeplink =[] #栈，存储压入的根节点 stack =[root] #print(len(stack)) #栈，存储压入的根节点的深度 stack2 =[1] if stack[0]: deep =1 #前序遍历 while stack!=[None]and stack: #弹出压入的节点 node = stack.pop() #记录遍历到的节点 res.append(node.val) #记录遍历到的节点的深度 deeplink.append(deep) #压入根节点的子节点和对应深度 if node.right: stack.append(node.right) stack2.append(deep+1) if node.left: stack.append(node.left) stack2.append(deep+1) #弹出压入栈的深度 deep = stack2.pop() if deeplink: return max(deeplink) else: return 0 下面是层次遍历，不同的地方在于出栈的时候，先进先出 class Solution: def maxDepth(self, root: TreeNode) -> int: count = 0 stack = [root] print(stack) while stack and stack!=[None]: count +=1 size = len(stack) while size: size -=1 #先进先出，自上而下 node = stack.pop(0) if node.right: stack.append(node.right) if node.left: stack.append(node.left) return count 最后用递归求解 class Solution: def maxDepth(self, root: TreeNode) -> int: if root==None: return 0 count1 = self.maxDepth(root.right)+1 count2 =self.maxDepth(root.left)+1 return (max(count1,count2)) 五行代码结束了。。。。。。。。。。。。。。。。。。。。。 每次执行函数都有三种可能，没有子节点，一个子节点，两个子节点。操作是两种，没有子节点返回0，有一个子节点就相应的路径加1。最后返回这个叉口最大的深度。整个遍历过程，就是沿着最右边的路径走，然后返回，一个接一个地走完。 |
|
|
来自： 昵称48979411 > 《待分类》
