老师好,关于二叉树遍历的递归算法:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
if(p== null && q == null) return true;
if(p==null || q==null) return false;
if(p.val!= q.val) return false;
return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}
}
因为之前关于递归只讲了阶乘的例子,所以这里用true or false时候并不太懂,主要有两个问题:
(1)
当左右节点的深度不同时,最终的判断的终止条件在哪里?
比如一个二叉树,它的左子树(p)的深度为2,右子数(q)的深度为5.(如下图)
那么,该递归的终止条件,是深度为2时,p.left p.right都是为null,跳出递归?还是到深度为5时,q的子节点也都遍历完成后,才跳出递归?

(2)
关于boolean类型递归是如何作用的。
之前关于递归只讲到阶乘,是递归直到调用到n=1 return 1, 才会一点点向上返回每次递归调用的值。

但是,这里就不是很懂是如何作用的,假设只有最后的p.left和q.left不同,(如下图)
那么,是如阶乘的算法一样,第一层是先开始isSameTree()方法,
到第二层后,判断为false && true, 所以return false,
然后关闭第二层栈堆,然后到第一层, 判断为 true && true, return true
最后结束程序?
那么这样的话,不就是return了两个值?分别是false和true?
这里的递归倒是是怎么作用的?谢谢
