Talking Recursively Part I : Tree
初衷和定位
写本篇分享的初衷是我自己在写过一些Leetcode树的题目的基础上，针对自己前期对于递归的认识还有对于树的概念的进行的总结。
本篇分享适用于已经接触了一些Leetcode树方面和递归相关内容的题目，但是一筹莫展，头疼不已的人，通过对一些比较有意思的Leetcode题目进行分析，希望让读者有新的认识。
内容分布
Tree这一个部分分成两个Section：
Section A：对于二叉树，树的概念和基本操作进行一个归纳和整理，同时希望能够从这些基本操作中提取出对于递归和尾递归程序的子问题划分、以及递归出口的设计的一个基本的设计思路。
Section B：浅谈一下二叉搜索树的相关问题。
Section A：递归和树
题目列表：
二叉树和树的基本概念
二叉树： 每一棵二叉树最多只有两棵子树，分别称为左子树和右子树（可以只有一棵子树，左子树或者右子树，或者没有子树），而且左右子树的次序不能随便交换。空子树一般也被认为是二叉树。
二叉树的定义并没有像普通的『描述性』定义一样，通过描述介绍一个事物本身来让读者认识。这样的定义方法其实是一种『递归定义』，而且这样的定义具有一定的自解释性。
常见的递归定义还有著名的GNU操作系统，GNU也是一个递归定义：
GNU's Not Unix!
它和二叉树的定义一样，将自己本身作为定义的一个『子部分』。
同理，树的定义就是不止有两个节点可能有更多节点的树。
递归函数
斐波拉契数列：
int fib(int n){
if(n == 0) return 0;
if(n == 1) return 1;
return fib(n-1) + fib(n-2);
}
所以递归函数是一种调用自身的函数，这个函数而且不是一般的递归函数，他的递归调用的过程在这个函数的末尾，这样的函数而且还被称为尾递归函数。
递归函数的三要素
很明显完成第一个递归函数需要三要素：
- 是否需要返回值
- 分析子问题
- 设计递归出口
二叉树深度优先遍历
既然二叉树是一种递归定义的数据类型，不妨使用递归的方式对其进行遍历操作：
二叉树的数据类型：
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;
}
}
前序遍历：
void dfs(TreeNode node){
if(node == null) return ;
// process(...)
dfs(node.left);
dfs(node.right);
}
回顾了二叉树的深度优先遍历的几种方式之后，我们来看一道题目：
我们引入『三要素分析法』进行递归程序的分析：
- 返回值：看起来可以直接使用递归遍历的模板，不需要返回值
- 子问题： 将节点root的左右两节点进行翻转
- 递归出口：如果是遇到了空节点，直接返回
这道题可以直接通过遍历的过程直接完成递归操作。常见的二叉树的前中后序遍历他们的区别就在于process()的位置。
class Solution {
private void helper(TreeNode node){
if(node == null) return;
// 将下面三个操作抽象为process 是一个前序遍历的过程
TreeNode temp = node.left;
node.left = node.right;
node.right = temp;
helper(node.left);
helper(node.right);
}
public TreeNode mirrorTree(TreeNode node) {
helper(node);
return node;
}
}
这道题使用前序和后序遍历都是可以的，这道题可以使用中序遍历吗？
求N叉树的后序遍历
二叉树的后序遍历：
void dfs(TreeNode node){
if(node == null) return ;
dfs(node.left);
dfs(node.right);
// process(...)
}
根据N叉树的节点结构不难想到，process过程应该在整体的遍历过程的后面。
- 返回值：void
- 子问题：依次遍历这个节点root的子树children（List<Node> children）中的节点和这个节点的子树的所有非null节点，
- 递归出口：当遍历到的此节点为null
class Solution {
List<Integer> result = new LinkedList<>();
public void helper(Node node){
if(node == null) return ;
for (int i = 0; i < node.children.size(); i++) {
helper(node.children.get(i));
}
result.add(node.val);
}
public List<Integer> postorder(Node root) {
helper(root);
return result;
}
}
层次遍历
层次遍历也叫做广度优先遍历，虽然这种方法不是递归的方法，但是还是要提一下：
二叉树的深度
求二叉树的最大深度
首先给出二叉树深度的定义：定义没有子树的节点（叶子节点）的深度为1，其他的节点的深度为左右子树的深度的最大值加1。
-
求二叉树的最大深度
很明显上面的定义正好符合这道题的题目需要的算法。
这道题和前面的两道题不同的地方在于，这个递归程序的是具有返回值的。一个具有返回值的递归程序它相对于没有返回值的程序当我们使用『要素分析法』的时候可以明白： - 返回值：有！
- 递归出口：当节点为空时；返回多少？
- 子问题：求左子树和右子树的深度的最大值加1
class Solution {
// https://leetcode-cn.com/explore/interview/card/top-interview-questions-easy/7/trees/47/
public int maxDepth(TreeNode node) {
if(node == null) return 0;
return Math.max(maxDepth(node.left), maxDepth(node.right)) + 1;
}
}
这样的递归程序需要
- 明确程序的返回值的语义
- 明确递归出口的返回值的语义
二叉树的最小深度
-
二叉树的最小深度
这道题的代码可以这样写吗？
class Solution {
public int minDepth(TreeNode root) {
if(root == null) return 0;
// 求左右的最短深度
int m1 = minDepth(root.left);
int m2 = minDepth(root.right);
return Math.min(m1,m2 ) +1;
}
}
对付二叉树问题，可以从以下四种情况思考递归出口（穷举法）：
上面的算法明显对只有一个节点的情况会失效：
正确的算法：
class Solution {
public int minDepth(TreeNode root) {
if(root == null) return 0;
int m1 = minDepth(root.left);
int m2 = minDepth(root.right);
if(root.left == null || root.right == null) return m1 + m2 + 1;
return Math.min(m1,m2 ) +1;
}
}
使用helper 函数 + 全局变量
前面的所有的递归函数都直接调用了Leetcode 给出的题目中的函数本身，但是有些时候因为在递归过程中递归函数的返回值，参数等等会有不同的情况，所以此时会引入『helper』函数。
二叉树的堂兄弟节点
-
二叉树的堂兄弟节点
堂兄弟节点一定是在同一层（深度相同）但是父母不同的节点，可以通过使用外部变量parent（用于记录节点的父母节点），depth（用于记录节点的深度的值）这两个变量来完成这道题，在完成深度优先搜索之后，观察返回的结果是不是父母不同，而且depth相同。 - 返回值：无
- 子问题：
- 记录这个节点的父节点
- 深度虽然可以使用参数的方法进行记录，但是在最后比较的时候没有方法比较父母节点是否相同。
class Solution {
private HashMap<Integer, Integer> depth = new HashMap<>();
private HashMap<Integer, TreeNode>parents= new HashMap<>();
private void dfs(TreeNode node, TreeNode parent){
if(node == null) return ;
depth.put(node.val, parent == null ? 0 : depth.get(parent.val) +1 );
parents.put(node.val, parent);
dfs(node.left, node);
dfs(node.right, node);
}
public boolean isCousins(TreeNode root, int x, int y) {
dfs(root, null);
return depth.get(x).equals(depth.get(y)) && parents.get(x) != parents.get(y);
}
}
寻找重复的子树
- 返回值：需要返回值；返回这棵树和其子树对应的value
- 子问题：
- 将这个节点进行序列化
- 同种类型的子树使用一种value表示
- 当子树出现的次数为2时，放入最终结果
- 递归出口：当节点为空时，返回0
序列化
序列化一个二叉树的方法有很多，最常见的方法是通过前中后序遍历形成的字符串作为序列化结果。对于这道题而言，使用这样的方法会包含很多冗余信息，而且序列化不是这道题的主要目的。
将一棵二叉树表示为一个三元组（node.val, f(left), f(right)）, 左侧和右侧子树的序列化结果都使用一个数字来表示。
可以通过使用两个哈希表来结题。其中trees<String,Integer>中的value表示这子树root对应的值；count<Integer,Integer>其中count的key由序列化的字符串对应的数字决定，value表示子树root出现的次数。
具体代码如下：
class Solution {
int t = 1;
Map<String, Integer> trees = new HashMap();
Map<Integer, Integer> count = new HashMap();
List<TreeNode> ans = new ArrayList();
public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
dfs(root);
return ans;
}
//使用了helper函数
public int dfs(TreeNode node) {
if (node == null) return 0;
String serial = node.val + "," + dfs(node.left) + "," + dfs(node.right);
// computeIfAbsent = 在map中找，如果为空就存入，并且返回存入之后的结果
int uid = trees.computeIfAbsent(serial, x-> t++);
//是否有重复的子树（序列化之后）
count.put(uid, count.getOrDefault(uid, 0) + 1);
if (count.get(uid) == 2)
ans.add(node);
return uid;
}
}
小结
实际运用
将二叉树转换为链表
这道题的侧重点在子问题的设计上：
返回值：不需要
-
子问题：对于当前的root节点
- 将左侧侧节点展平为链表
- 将右侧节点展平为链表
- 缓存展平了的root右侧节点，将左侧节点连接在root节点的右侧
- 将缓存的右侧节点连接在左侧节点的尾部
递归出口：root为空
class Solution {
public void flatten(TreeNode root) {
if(root == null)return ;
flatten(root.left);
flatten(root.right);
TreeNode temp = root.right;
root.right = root.left;
root.left = null;
while(root.right != null) root = root.right;
root.right = temp;
}
}
对称二叉树
后面两题讲一个小技巧。
-
对称二叉树
思路：当且仅当节点root的左子树是一个对称二叉树并且右子树也是一个对称二叉树时，节点root代表的树是一个对称二叉树。 - 返回值：boolean 表示这个子树是否是一个对称二叉树
- 子问题：求证root.left.right 和 root.right.left 是不是相同的值 && root.right.right 和 root.left.left 是不是相同的值
- 递归出口：root为空 返回true
class Solution {
private boolean helper(TreeNode left, TreeNode right){
if(left == null && right == null) return true;
if(left == null || right == null || left.val != right.val) return false;
return helper(left.left , right.right) && helper(left.right, right.left);
}
public boolean isSymmetric(TreeNode root) {
if(root == null) return true;
return helper(root.left, root.right);
}
}
这道题比较简单，但是需要谈一谈被我称为条件的『过筛和归并』的技巧：
翻转等价二叉树
-
翻转等价二叉树
思路：同时遍历两棵树，如果出现不相同的情况，进行翻转，如果翻转之后还是不能相同，返回false。
通过枚举二叉树出现的情况，我们可以通过判断二叉树的孩子节点的情况对解空间进行剪枝，不然情况组合起来讨论会非常复杂。因为这道题没有说结果中需要两棵树结构相同，所以我们可以在翻转的时候，直接交换比较的两个指针（做一个假的翻转操作）。
- 返回值：boolean 表示这两颗二叉树是否是等价的
- 子问题：遍历这两棵树，如果不相同的时需要进行翻转
- 递归出口：
- 两棵树的指针同时为空：这棵子树遍历完成，没有异常是等价的
- 其中有一个指针为空，说明即使翻转了也无效，两棵子树不等价
- 当前的两个节点的值不相等，这种情况是在翻转之后发生的，说明不等价
显然，2 3 两种情况可以『归并』到一个表达式中
class Solution {
public boolean flipEquiv(TreeNode root1, TreeNode root2) {
//递归终止条件
if(root1==null&&root2==null)
return true;
if(root1==null||root2==null||root1.val!=root2.val)
return false;
//处理只存在一个孩子
if(root1.right == null && root2.right == null)
return flipEquiv(root1.left ,root2.left);
if(root1.left==null&&root2.left==null)
return flipEquiv(root1.right,root2.right);
if(root1.left==null||root2.left==null)
return flipEquiv(root1.left,root2.right)&&flipEquiv(root1.right,root2.left);
//处理左右孩子都存在
if(root1.left.val!=root2.left.val) return flipEquiv(root1.left,root2.right)&&flipEquiv(root1.right,root2.left);
return flipEquiv(root1.left,root2.left)&&flipEquiv(root1.right,root2.right);
}
}
这道题和上面一样，也通过了表达式的串联进行了情况的筛除：
