今天在刷算法题的时候,有一道剑指offer上的题目:重建二叉树,其中要先对给的两个int型数组判空,但是测试发现我写的判空方法不行,特此记录
【剑指offer】重建二叉树 --Java实现
递归构建二叉树
1. 分析
根据中序遍历和前序遍历可以确定二叉树,具体过程为:
- 根据前序序列第一个结点确定根结点
- 根据根结点在中序序列中的位置分割出左右两个子序列
- 对左子树和右子树分别递归使用同样的方法继续分解
例如:
前序序列{1,2,4,7,3,5,6,8} = pre
中序序列{4,7,2,1,5,3,8,6} = in
- 根据当前前序序列的第一个结点确定根结点,为 1
- 找到 1 在中序遍历序列中的位置,为 in[3]
- 切割左右子树,则 in[3] 前面的为左子树, in[3] 后面的为右子树
- 则切割后的左子树前序序列为:{2,4,7},切割后的左子树中序序列为:{4,7,2};切割后的右子树前序序列为:{3,5,6,8},切割后的右子树中序序列为:{5,3,8,6}
- 对子树分别使用同样的方法分解
代码如下 1 /**
2 * Definition for binary tree 3 * public class TreeNode { 4 * int val; 5 * TreeNode left; 6 * TreeNode right; 7 * TreeNode(int x) { val = x; } 8 * } 9 */ 10 import java.util.Arrays; 11 public class Solution { 12 public TreeNode reConstructBinaryTree(int [] pre,int [] in) { 13 //思路: 14 //根据先序可以确定根节点pre[0],然后根据中序将整个树分为左右子树,最后分别对左右子树在进行相同的方法,也就是递归即可
15 if( (pre.length == 0 ||pre==null ) || (in.length== 0|| in== null)){ 16 return null; 17 } 21 TreeNode res = new TreeNode(pre[0]); 22 for(int i=0;i< in.length;i++){ 23 //根据先序可以确定根节点pre[0],然后根据中序将整个树分为左右子树,最后分别对左右子树在进行相同的方法,也就是递归即可 24 //如果找到了某一个中序的节点 25 if(in[i] == pre[0]){ 26 //Arrays.copyOfRange(array,from,to);复制数组范围,包含from,但不包含to,也就是左闭右开 27 //左子树 28 res.left = reConstructBinaryTree( 29 Arrays.copyOfRange(pre,1,i+1),Arrays.copyOfRange(in,0,i) 30 ); 31 //柚子树 32 res.right = reConstructBinaryTree( 33 Arrays.copyOfRange(pre,i+1,pre.length),Arrays.copyOfRange(in,i+1,in.length) 34 ); 35 break; 36 } 37 } 38 return res; 39 40 } 41 }
》这是我写的判空,就是直接用是否等于null判断的,发现会报以下错误:
if( pre==null || in== null) {
return null;
}
》而写成下面这种用数组长度判断的时候,不会报错。
if
(pre.length ==
0
|| in.length ==
0
) {
return
null
;
}
》最终,我把两种写法合并,都进行判断,写成了下面的形式,也不会报错,这就很奇怪。
if( ( pre.length == 0 || pre == null ) || (in.length == 0|| in == null)){
return null;
}
我先记下来吧,以后最好都用这种判空,保险一些!原理还不太清楚,如果有知道的大佬,可以留言告知一下,谢谢!