二叉树查找的递归终结问题

1. 由labuadong的前中后序套路，修改成java版本

public void threeOrderTraverse(){
   System.out.println("前序遍历");
   if (this.left != null) {
     this.left.threeOrderTraverse();
   }
   System.out.println("中序遍历");
   if (this.right != null) {
     this.right.threeOrderTraverse();
   }
   System.out.println("后序遍历");
}

2. 二叉树的前中后序查找

关键点在于：如何把找到的结点层层返回

以中序查找为例子
Step 1：修改函数名、变量名

class Node{
   int no;
   Node left;
   Node right;
}

public Node inOrderSearch(){
   if (this.left != null) {
     this.left.inOrderSearch();
   }
   System.out.println("中序遍历");
   if (this.right != null) {
     this.right.inOrderSearch();
   }
}

Step 2: 增加业务代码，把参数加进来

public Node inOrderSearch(int no){
   if (this.left != null) {
     this.left.inOrderSearch();
   }
   
   if (this.no == no) {
     return this;
   }   

   if (this.right != null) {
     this.right.inOrderSearch();
   }
}

Step 3: 新建一个接收返回值的变量

public Node inOrderSearch(int no){
   Node resNode = null;
   if (this.left != null) {
     resNode = this.left.inOrderSearch(no);
   }
   
   if (this.no == no) {
     return this;
   }   

   if (this.right != null) {
     resNode = this.right.inOrderSearch(no);
   }
   
   // 如果找不到还是要返回null值
   return resNode;
}

Step 4: 加上一段拦截代码
拦截代码的作用：
若我们找到了结点，则说明返回变量 resNode != null，则可根据以 resNode != null 为条件，接力返回该结点。深层次理解的话，分为找到结点的这层栈的变化，以及没找到结点的其他层栈的变化，这个变化重点在于返回的对象是

1. 继续递归 -- 中间结点
2. null -- 叶子结点
3. this -- 目标结点
4. resNode -- 接力目标中间变量

public Node inOrderSearch(int no){
   Node resNode = null;
   if (this.left != null) {
     resNode = this.left.inOrderSearch(no);
   }
   // 拦截代码块
   if (resNode != null) {
     return resNode;
   }
  
   if (this.no == no) {
     return this;
   }   

   if (this.right != null) {
     resNode = this.right.inOrderSearch(no);
   }

   // 如果找不到还是要返回null值
   return resNode;
}