请教一下关于空指针null的问题，为什么每次都要先检查null呢？

bzoot 发表于 2020-8-22 16:36
所有人都在讲递归算法…我第一反应是如果不检测null，null.right会报错…
遍历tree是不断寻找节点的子节点 ...

有道理，后面的null.right会报错。。

是不是也可以通过，检查子节点是不是null的方式，进行遍历？

liuzz10 发表于 2020-8-22 16:43
有道理，后面的null.right会报错。。

是不是也可以通过，检查子节点是不是null的方式，进行遍历？

当然可以。

1. if (null != node.left) { TreeNode left = recursion(node.left); }
   
2. if (null != node.right) { TreeNode right= recursion(node.right); }

复制代码

liuzz10 发表于 2020-08-22 17:43:26
有道理，后面的null.right会报错。。

是不是也可以通过，检查子节点是不是null的方式，进行遍历？

其实是可以的，可以判断如果左右都是null，返回当前节点。如果左边不是null，走左边。右边不是null，走右边。这样的话，就3个base case，整体代码就不这么整洁了。而且这样还漏掉了root本身可能是null的情况。

楼主看来刚接触这类题目。

递归函数如果没有退出条件，会因为不断调用自身导致栈无限增长，而这是不可能的，因为：
1. 计算机的栈大小有上限。
2. 你输入的测试用例，大小是有限的，不可能需要一个无限的算法去模拟。

所以你一定：
1. 需要一个退出条件
2. 退出条件符合你的测试用例。

以二叉树为例，退出条件应该是服从，“如果当前节点是空结点，那么不需要再递归访问子节点”,也可以是“如果当前节点是叶子🍃结点，那么不需要再递归访问子节点”,这两者都是可以的。

答案里用的是前者。


如果你是递归访问一个图，那终止条件，就是“当前经被访问过了”

hamstersun 发表于 2020-8-23 11:02
楼主看来刚接触这类题目。

递归函数如果没有退出条件，会因为不断调用自身导致栈无限增长，而这是不可能的 ...

是的，第一次做tree相关的题。。谢谢你的总结，我今后做题的时候就知道怎么用啦

递归的思想， 主问题可以分解成两个子问题，树的左子树 和右子树；root.left and root.right;
TreeNode left= invertTree(root.left) 返回invert 好的左子树跟节点；
TreeNode right = invertTree(root.right) 返回invert 好的右子树跟节点；

这两个子问题和主问题的联系就是通过 root.left = right 和 root.right = left 完成整个问题的解决；

问题的终止条件就是当子问题的输入是null的时候（通过有限次操作就能完成）就返回；

lujingyang1029 发表于 2020-8-23 21:20
递归的思想， 主问题可以分解成两个子问题，树的左子树 和右子树；root.left and root.right;
TreeNode le ...

谢谢您非常清晰的解释，我理解了~