关于二叉树深度求助

Question

在对二叉树深度计算的算法

reeDepth(self , pRoot):
        if pRoot == None:
            return 0;
        lDepth =  Solution.TreeDepth(self , pRoot.left);
        rDepth =  Solution.TreeDepth(self , pRoot.right);
        return max(lDepth , rDepth) + 1 

请问lDepth和rDepth是怎么递归的，为什么会返回的是一个数，谢谢！

Answer 1

之前的答案不小心删除了。
你贴的代码有问题，函数名少了一个T，原文应该是：

TreeDepth(self , pRoot):
        if pRoot == None:
            return 0;
        lDepth =  Solution.TreeDepth(self , pRoot.left);
        rDepth =  Solution.TreeDepth(self , pRoot.right);
        return max(lDepth , rDepth) + 1 

上述代码用自然语言描述就是pRoot的深度=max(pRoot左子树的深度,pRoot右子树的深度)+1。
第一个问题：lDepth和rDepth是怎么递归的?
你想问的应该是pRoot左子树和pRoot右子树是怎么递归的？Python是动态类型语言，没有显式的类型声明。如果我们把树的类型定义为Tree，TreeDepth接受类型为Tree的参数，已知树的左子树和右子树的类型也是Tree，TreeDepth(self, pRoot.left)和TreeDepth(self, pRoot.right)也会执行函数的全部代码，即函数声明中的pRoot依次替换为pRoot.left和pRoot.right。这个过程一直进行到叶子结点【叶子结点没有子树，故返回】，然后回溯。
第二个问题：为什么返回一个数？
可以这么看：TreeDepth有两个return，每个return都返回整数，所以函数的返回类型是整数。你可能会对lDepth和rDepth为什么是整数有疑问，你可以用例子套一下，在回溯时，树的深度实际上是由0+1+1+...相加得到。比较正式的证明方法是数学归纳法。
附推导过程，TD是TreeDepth的缩写，由图看出，每一层都会调用max。

Answer 2

其实这是对递归的陌生引申出的问题. 大致上递归函数满足两个性质

• 终止条件, 这里是

        if pRoot == None:
            return 0;

• 每次递归需要对某个(些)参数做出改变, 这样才能离终止条件更近, 这里而这里就是proot在变(虽然self也变, 不过proot的变化才能让你抵达终止条件).

具体到你这个例子的理解, 你自己画几个节点, 然后纸上人肉模拟下算法的过程, 就很容易理解了.

二叉树的很多算法描述都是用递归的, 当然, 不用递归也可以, 只是往往没有递归看起来那么优雅.