【数据结构】二叉树的递归

数据结构系列三：二叉树(二)

一、递归的原理

1.全访问

2.主角

3.返回值

4.执等

二、递归的化关系思路

三、递归的方法设计

---

一、递归的原理

1.全访问

方法里调用方法自己，就会形成调用方法本身的一层一层全新相同的调用，方法的形参设置为根的左右子根访问，方法调用时就会自动去访问一次树的左右根，一个方法根会调用里面方法访问它的左右子根、而调用着的是两个全新和它相同的、属于着它的方法，下一层的左子根同样会去调用着属于它的它下一层的左右子根两方法，下一层的右子根也同样会去调用着属于它的它下一层的左右子根两方法，每一个全新的方法都会去调用着属于在它里面的它下一层左右子根的两个全新相同的也会去调用它们各自左右子根两全新相同的方法，这样每个根方法里面都会有对应的同样访问两子根方法本身再去调访问它左右子根的又左右子根的相同方法，从上到下每个根都会被属于进而被调用着、去调用着而被全访问到

---

2.主角

从上到下每个根都有去被调用成方法的形参做方法的主角，除了最上层根没有上层不被作子角被带着、最下层null作主角里面却不带有子角，每个根都会作主角里面带着子角、被作子角被上层主角带着

---

3.返回值

主角最重要的是它方法的返回值，主角里调用产生属于它的子主角卡等着执等着子主角执行完后成返回值，当null成主角时会直接成为返回值，每一个主角成返回值都会促使上层主角变着成返回值也再去促使着它再上一层主角也成返回值也去促使着上层：

从下往上汇着促着主角们从下往上推着翻着成为返回值，最后全部变为返回值推着到最上层的也成一个返回值最后结束

---

4.执等

每个主角们卡着执着等着左右根主角都是先执等着进左主角再执等着进右主角等返回值的：

• 如果执等的主角是null，进去null作为主角的方法是立即成返回值的使得执等着null的主角是能立马得到返回值促使的
• 如果执等的主角是根主角，进去根节点作为主角的往往它变成返回值需要长时间的回应使得执卡着的

---

二、递归的化关系思路

因为主角们都是完全相同性质的主角，主角最后都是返回值都是结果，然后结构都是上一层的一个结果用它下一层的两个结果化得到再两层两层无缝循环作为结果与另一个结果再拼接再化成上一层的一个结果，结构都是下一层的两结果化为上一层的一个结果一层上一层、重复地往上化，所以只要知道了上一层的一个结果与下一层的两个结果之间的化关系在此种结构下就能设计成循环地向上化出结果

三、递归的方法设计

知道上一层结果与下一层的两结果之间的化关系后从最下两层开始：

1. 先设计就只有这两层的倒2层是总结果的化设计
2. 设计好后再设计再往上多一层跳到它这层主角里面对刚已设计好的下层的主角返回值接收处那边再设计

从最下两层的设计再往上爬上两层的设计，递归方法就总体设计好了