老师，Traverse()方法循环调用流程不太明白

Question

老师，这个方法我不太明白
1.当把root对象传到这个一个方法后，会先判断是否nil，不是的话就先把Left左边这个对象指针传进去重新调用这个方法，但是我感觉是循环调用了这个方法，没走到Print()这一步呀
2.就是return后为什么不是终止了这个程序，而是跳过当前nul的指针，继续往下遍历呢，能不能把过程说下，我用DEBUG去看，看不出来

Answer 1

ccmouse 2020-09-24 18:43:59

这里是一种递归调用

递归调用的时候，这个node就不再是原本的node，而是它的左儿子。然后继续递归，node就变成了左儿子的左儿子。再递归，就变成左儿子的左儿子的左儿子，然后发现node==nil, return。但这里return的只是左儿子的左儿子的左儿子的遍历。接下来继续遍历左二子的左儿子。这里我截了调试器的图：

我用的是vscode，不过intelliJ或是goland会更好用，我们在红框return处断点。这里就是第一次命中。我们一定要关注call stack和node.Value的值。这个Traverse函数被调用了三遍，这个node参数因此也有三份。我们这里看到的是根结点，值是3。

第二层递归调用，访问根结点的左儿子(node.Left.Traverse)，3的左儿子是0，因此在这里node.Value是0

第三层递归调用，这里node是nil，因此没有node.Value，函数也将返回。

我们如果往下走一步：

第三层return以后只是返回到第二层，也就是node.Value是0这一层，这里的代码如下，此时的状态是：

node.Left.Traverse() // <- 已经执行完毕

node.Print()             // <- 输出0

node.Right.Traverse()  // <- 输出0之后遍历右儿子，遍历完成后本节点“0”极其所有儿子遍历完毕，退到第1层，节点值是“3”这层。

总结，如果没有学习过递归，的确理解起来会有困难，调试器是一个很好的方法，但每时每刻都要关注call stack和node.Value，一定牢记它调用了很多层，有很多个node，每个node值都不一样，顺着这个顺序在旁边的纸上画一下目前进行到哪一步。

• 提问者 Yao_Jerry #1

  谢谢老师，我大概明白了，之前是以为return肯定会终止程序的，怎么想也不明白。老师讲得很详细，辛苦了