二叉树的递归套路

我要就业

Created At : 2022-07-08 08:56

Count:3.8k Views 👀 :

二叉树的递归套路

二叉树的递归套路

简述
1. 可以解决面试中的绝大部分二叉树(95%以上)的问题，尤其是树形dp问题
2. 其本质是利用递归遍历二叉树的便利性，每个节点在递归的过程中可以回到该节点3次
具体步骤为：
1. 假设以X节点为头，假设可以向X左树和右树要任何信息
2. 在上一步的假设下，讨论以X为头结点的树，得到答案的可能性（最重要）
  1. 常见分类
    1. 与X无关的答案
    2. 与X有关的答案
3. 列出所有可能性后，确定到底需要向左树和右树要什么样的信息
4. 把左树信息和右树信息求全集，就是任何一颗子树都需要返回的信息S
5. 递归函数都返回S，每颗子树都这么要求
6. 写代码，在代码中考虑如何把左树信息和右树信息整合出整棵树的信息
Base cases:
1. The base case is also called a stopping condition for recursive calls. It is very important to have a base case for every recursive code.

给定一棵二叉树的头结点head，返回这颗二叉树是不是平衡二叉树

Code03_IsBalanced
题目解释:
1. 平衡树概念：在一棵二叉树中，每一个子树，左树的高度和右树的高度差不超过1
以X为头的树的可能性，要做到平衡，需要的条件是
1. X左树平衡，
2. 右树平衡，
3. X的左树高度和右树高度差不超过1
4. 对左树的要求:
  1. 返回:是否平衡
  2. 返回:高度
5. 对右树的要求:
  1. 返回:是否平衡
  2. 返回:高度
如果想用递归,需要左右都索要相同信息求全集,也就是他们给的信息的并,所以该题,我们X需要向左右子树要的信息Info为，
1. 是否平衡public boolean isBalanced;
2. 高度public int height;

// 左右要求一样，Info信息返回的结构体
public static class Info {
    public boolean isBalanced;
    public int height;

    public Info(boolean i, int h) {
        isBalanced = i;
        height = h;
    }
}

public static Info process(Node x) {
    if (x == null) {
        return new Info(true, 0);
    }
    // 假设左树可以给信息
    Info leftInfo = process(x.left);
    // 假设右树可以给信息
    Info rightInfo = process(x.right);
    // 整棵树的高度
    int height = Math.max(leftInfo.height, rightInfo.height) + 1;
    // 该树是否平衡，先假设true，再用条件进行判断
    boolean isBalanced = true;
    if (!leftInfo.isBalanced) {
        isBalanced = false;
    }
    if (!rightInfo.isBalanced) {
        isBalanced = false;
    }
    if (Math.abs(leftInfo.height - rightInfo.height) > 1) {
        isBalanced = false;
    }
    return new Info(isBalanced, height);
}

返回二叉树任意两个节点最大值

Code06_MaxDistance
题目解释:
1. 给定一棵二叉树的头结点head，任何两个节点之间都存在距离，返回整棵二叉树的最大距离
2. 两个节点之间的距离:两个节点中最精简的路径上存在的节点数
以X为头的树的可能性(常见的分类)
1. 有可能最大距离和当前节点X无关(最大距离不通过X)
  1. 最大距离是X左树的最大距离,或者,右树的最大距离
  2. 需要选出max(左树最大距离,右树最大距离)
2. 最大距离跟X有关，
  1. 即最大距离通过X
  2. 左树离X最远的点,到,X右树上离X最远的点。
  3. 即X左树的高度,加上,X自身高度1,加上,X右树上的高度
3. 对左树的要求:
  1. 返回整棵树最大距离
  2. 返回高度
4. 对右树的要求:
  1. 返回整棵树最大距离
  2. 返回高度
结论：根据递归套路，我们每次递归，需要返回X左树的最大距离和高度，同理返回X右树的最大距离和高度。
Info求并集
1. 最大距离
2. 高度

返回二叉树中的最大的搜索二叉树的大小Size

Code05_MyMaxSubBSTSize
题目解释:
1. 给定一颗二叉树，返回这颗二叉树中最大的二叉搜索树的Size
2. 搜索二叉树概念：整颗树上没有重复值，左树的值都比我小，右树的值都比我大。每颗子树都如此。
以X为头的树的可能性(常见的分类)
1. 与X无关:最终找到的搜索二叉树，不以X为头
  1. 左树满足搜索二叉树的大小/节点个数
  2. 右树满足搜索二叉树的大小/节点个数
2. 与X有关:最终找到的搜索二叉树，以X为头
  1. X的左树整体是搜索二叉树
  2. X的右树整体是搜索二叉树
  3. 左树的最大值小于 X
  4. 右树的最小值大于 X
列出需要信息:
1. 左树
  1. 最大搜索二叉树的子树的大小size
  2. 左树整体是不是搜索二叉树 isAllBST
  3. 左树最大值
2. 右树:
  1. 最大搜索二叉树的子树的大小size
  2. 右树整体是不是搜索二叉树 isAllBST
  3. 右树最小值
总结Info
1. size
2. isAllBST
3. max
4. min

派对最大快乐值

Code04_MaxHappy
排队最大快乐值问题，员工信息定义如下，多叉树结构：

class Employee{
    // 这名员工可以带来的快乐值
    public int happy;
    // 这名员工有哪些直接的下级
    List<Employee> subordinates;
}

题目解释:
1. 每个员工都符合Employee类的描述，整个公司的人员结构可以看作是一颗标准的，没有环的多叉树。
2. 树的头结点是公司唯一的老板。除了老板外的每个员工都有唯一的直接上级。
3. 叶节点是没有任何下属的基层员工（subordinates为空），除了基层员工股外，每个员工都有一个或多个直接下级。
4. 现在公司要来办party，你可以决定哪些员工来，哪些员工不来，
5. 规则:
  1. 如果某个员工来了，那么这个员工的所有直接下级都不能来
6. 排队的整体快乐值是所有到场员工的快乐值的累加
7. 你的目标:
  1. 让派对的整体快乐值尽量的大
8. 给定一颗多叉树头结点boss，请返回排队的最大快乐值
以X为头的树的可能性(常见的分类)(假设X有三个员工,分别为firstChild,secondChild,thirdChild)
1. X不来
  1. 0
  2. max{firstChild来的最大快乐值,firstChild不来的最大快乐值,}
  3. max{secondChild来的最大快乐值,secondChild不来的最大快乐值,}
  4. max{thirdChild来的最大快乐值,thirdChild不来的最大快乐值,}
  5. 相加
2. X来
  1. X.happy
  2. X.firstChild 不来的情况下:整棵树的快乐值
  3. X.secondChild 不来的情况下:整棵树的快乐值
  4. X.thirdChild 不来的情况下:整棵树的快乐值
  5. 相加
Info:
1. X来的情况下,整棵树的最大快乐值
2. X不来的情况下,整棵树的最大快乐值

判断二叉树是否是满二叉树

题目解释:给定一棵二叉树的头结点head，返回这颗二叉树是不是满二叉树。

第一种方法

思路：
1. 满二叉树一定满足2^L - 1 == N，其中L是这颗二叉树的高度，N是这颗二叉树的节点个数

Info

public static class Info1 {
    // 以x为头节点的树的高度
    public int height;
    // 以x为头节点的树的节点数
    public int nodes;

    public Info1(int h, int n) {
        height = h;
        nodes = n;
    }
}

递归主程序:

// 递归进行时
public static Info1 process1(Node head) {
    if (head == null) {
        return new Info1(0, 0);
    }
    // 往左递归
    // 往右递归
    Info1 leftInfo = process1(head.left);
    Info1 rightInfo = process1(head.right);
    // 要信息：height
    int height = Math.max(leftInfo.height, rightInfo.height) + 1;
    // 要信息：nodes
    int nodes = leftInfo.nodes + rightInfo.nodes + 1;

    return new Info1(height, nodes);
}

第二种方法:

思路：
1. 左树满 && 右树满 && 左右树高度一样 -> 整棵树是满的

Info

public static class Info2 {
    public boolean isFull;
    public int height;

    public Info2(boolean f, int h) {
        // 收集子树是否是满二叉树
        isFull = f;
        // 收集子树的高度
        height = h;

    }
}

递归主程序:

// 递归主程序
public static Info2 process2(Node h) {
    if (h == null) {
        return new Info2(true, 0);
    }
    // 左树
    Info2 leftInfo = process2(h.left);
    // 右树
    Info2 rightInfo = process2(h.right);
    // 是否满
    boolean isFull = leftInfo.isFull && rightInfo.isFull && leftInfo.height == rightInfo.height;
    // 高度
    int height = Math.max(leftInfo.height, rightInfo.height) + 1;
    return new Info2(isFull, height);
}

判断二叉树是不是搜索二叉树

网课LeetCode摘录.md : 98. 验证二叉搜索树

返回二叉树中的最大的搜索二叉树的大小Size

返回二叉树中的最大的搜索二叉树的头节点

Code02_MaxSubBSTHead
题目解释:
1. 给定一颗二叉树，返回这颗二叉树中最大的二叉搜索树的头节点
2. 搜索二叉树概念：整颗树上没有重复值，左树的值都比我小，右树的值都比我大。每颗子树都如此。
以X为头的树的可能性(常见的分类)
1. 与X无关:最终找到的搜索二叉树，不以X为头
  1. 左树收集的答案
  2. 右树收集的答案
  3. 答案中较大的那个
2. 与X有关:最终找到的搜索二叉树，以X为头
  1. X的左树整体是搜索二叉树
  2. X的右树整体是搜索二叉树
  3. 左树的最大值小于 X
  4. 右树的最小值大于 X
列出需要信息:
1. 左树
  1. 最大二叉搜索子树的头节点
  2. 最大搜索二叉树的子树的大小size
  3. (是否是搜索二叉树,isAllBST,可由1得出)
  4. 左树最大值
2. 右树:
  1. 最大二叉搜索子树的头节点
  2. 最大搜索二叉树的子树的大小size
  3. (右树整体是不是搜索二叉树 isAllBST)
  4. 右树最小值
总结Info
1. head(isAllBST)
2. size
3. max
4. min

Info

// 每一棵子树
public static class Info {
    // 如果最大搜索二叉子树的头节点，就是传入的head，那么整棵树就是搜索二叉树
    public Node maxSubBSTHead;
    public int maxSubBSTSize;
    public int min;
    public int max;

    public Info(Node h, int size, int mi, int ma) {
        maxSubBSTHead = h;
        maxSubBSTSize = size;
        min = mi;
        max = ma;
    }
}

递归主程序:

public static Info process(Node X) {
    if (X == null) {
        return null;
    }
    // 左 信息
    Info leftInfo = process(X.left);
    // 右 信息
    Info rightInfo = process(X.right);
    int min = X.value;
    int max = X.value;
    Node maxSubBSTHead = null;
    int maxSubBSTSize = 0;
    if (leftInfo != null) {
        min = Math.min(min, leftInfo.min);
        max = Math.max(max, leftInfo.max);
        maxSubBSTHead = leftInfo.maxSubBSTHead;
        maxSubBSTSize = leftInfo.maxSubBSTSize;
    }
    if (rightInfo != null) {
        min = Math.min(min, rightInfo.min);
        max = Math.max(max, rightInfo.max);
        if (rightInfo.maxSubBSTSize > maxSubBSTSize) {
            maxSubBSTHead = rightInfo.maxSubBSTHead;
            maxSubBSTSize = rightInfo.maxSubBSTSize;
        }
    }
    if ((leftInfo == null ? true :
            // 左树是不是搜索二叉树
            (leftInfo.maxSubBSTHead == X.left && leftInfo.max < X.value)
    ) && (rightInfo == null ? true :
            // 右树是不是搜索二叉树
            (rightInfo.maxSubBSTHead == X.right && rightInfo.min > X.value)
            )) {
        maxSubBSTHead = X;
        maxSubBSTSize =
                (leftInfo == null ? 0 : leftInfo.maxSubBSTSize)
                +
                (rightInfo == null ? 0 : rightInfo.maxSubBSTSize)
                +
                1;
    }
    return new Info(maxSubBSTHead, maxSubBSTSize, min, max);
}

是否是完全二叉树

题目解释
1. 给定一棵二叉树的头结点head，返回这颗二叉树是不是完全二叉树
2. 若设二叉树的深度为k，除第 k 层外，其它各层 (1～k-1) 的结点数都达到最大个数，第k 层所有的结点都连续集中在最左边，这就是完全二叉树。
宽度优先遍历解决思路:
1. 如果用树的宽度优先遍历的话，
  1. 如果某个节点有右孩子，但是没有左孩子，一定不是完全二叉树
  2. 否则继续
2. 在1条件的基础上，
  1. 一旦遇到第一个左右孩子不双全的节点，后续所有节点必须为叶子节点
3. 代码

// 不要提交这个类
public static class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;

    public TreeNode(int v) {
        val = v;
    }
}

public static boolean isCompleteTree1(TreeNode head) {
    if (head == null) {
        return true;
    }
    LinkedList<TreeNode> queue = new LinkedList<>();
    // leaf：是否遇到过左右两个孩子不双全的节点
    boolean leaf = false;
    TreeNode l = null;
    TreeNode r = null;
    queue.add(head);
    // 标准的宽度优先遍历的代码
    while (!queue.isEmpty()) {
        head = queue.poll();
        l = head.left;
        r = head.right;
        if (
        // 如果遇到了不双全的节点之后，又发现当前节点不是叶节点
        (leaf && (l != null || r != null))

                ||
                // (有右无左)左孩子为空，右孩子不为空，则返回false
                (l == null && r != null)

        ) {
            return false;
        }
        if (l != null) {
            queue.add(l);
        }
        if (r != null) {
            queue.add(r);
        }
        if (l == null || r == null) {
            leaf = true;
        }
    }
    return true;
}

二叉树递归套路解法思路：(找是完全二叉树的所有情况)

满二叉树（无缺口），一定是完全二叉树。
1. 此时左右树需要给X的信息是，
  1. 是否是满的
  2. 高度
2. 如果左右树满，且左右树高度一样，那么就是该种情况:满二叉树,也就是完全二叉树
有缺口
1. 缺口可能停在我的左树上
  1. 左树需要给我是否是完全二叉树
  2. 右树需要给X是否是满二叉树
  3. 且左树高度比右树高度大1
2. 缺口可能在左右树的分界。左树是满的，右树也是满的，左树高度比右树大1
3. 左树已经满了，缺口可能在我的右树上。
  1. 左树是满的
  2. 右树是完全二叉树
  3. 且左右树高度一样
Info
1. 是否是完全二叉树
2. 是否是满二叉树
3. 高度

Info代码

public static class Info {
    public boolean isFull;
    public boolean isCBT;
    public int height;
    // 1. 是否是完全二叉树
    // 2. 是否是满二叉树
    // 3. 高度
    public Info(boolean full, boolean cbt, int h) {
        isFull = full;
        isCBT = cbt;
        height = h;
    }
}

递归代码

public static Info process(TreeNode x) {
    if (x == null) {
        return new Info(true, true, 0);
    }
    Info leftInfo = process(x.left);
    Info rightInfo = process(x.right);
    // 高度
    int height = Math.max(leftInfo.height, rightInfo.height) + 1;
    // 是否是满二叉树
    boolean isFull = leftInfo.isFull && rightInfo.isFull && leftInfo.height == rightInfo.height;
    // 是否是完全二叉树
    boolean isCBT = false;
    if (leftInfo.isFull && rightInfo.isFull && leftInfo.height == rightInfo.height) {
        isCBT = true;
    } else if (leftInfo.isCBT && rightInfo.isFull && leftInfo.height == rightInfo.height + 1) {
        isCBT = true;
    } else if (leftInfo.isFull && rightInfo.isFull && leftInfo.height == rightInfo.height + 1) {
        isCBT = true;
    } else if (leftInfo.isFull && rightInfo.isCBT && leftInfo.height == rightInfo.height) {
        isCBT = true;
    }
    return new Info(isFull, isCBT, height);
}

最低公共祖先

题目解释
1. 给一颗二叉树的头结点head，和另外两个节点a和b。返回a和b的最低公共祖先
2. 二叉树的最低公共祖先概念:任意两个节点，往父亲看，最开始交汇的节点，就是最低公共祖先
解法一：用辅助map，Key表示节点，Value表示节点的父亲节点。我们把两个目标节点的父亲以此放到map中，依次遍历

解法二：使用二叉树的递归套路。

Info

// 任何子树返回三个信息
public static class Info {
    public boolean findA;
    public boolean findB;
    // o1和o2的最初交汇点是谁，如果不是在这棵树上交汇的，返回null
    public Node ans;

    public Info(boolean fA, boolean fB, Node an) {
        findA = fA;
        findB = fB;
        ans = an;
    }
}

递归过程

public static Info process(Node x, Node a, Node b) {
    // base case
    if (x == null) {
        return new Info(false, false, null);
    }
    // 左树要来三个信息
    Info leftInfo = process(x.left, a, b);
    // 右树要来三个信息
    Info rightInfo = process(x.right, a, b);
    boolean findA = (x == a) || leftInfo.findA || rightInfo.findA;
    boolean findB = (x == b) || leftInfo.findB || rightInfo.findB;
    // o1和o2最初交互点在哪里
    Node ans = null;
    if (leftInfo.ans != null) {
        ans = leftInfo.ans;
    } else if (rightInfo.ans != null) {
        ans = rightInfo.ans;
    } else {
        if (findA && findB) {
            ans = x;
        }
    }
    return new Info(findA, findB, ans);
}

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达，可以邮件至 963614756@qq.com。

二叉树的递归套路

二叉树的递归套路

给定一棵二叉树的头结点head，返回这颗二叉树是不是平衡二叉树

返回二叉树任意两个节点最大值

返回二叉树中的最大的搜索二叉树的大小Size

派对最大快乐值

判断二叉树是否是 满二叉树

判断二叉树是不是 搜索二叉树

返回二叉树中的最大的搜索二叉树的大小Size

返回二叉树中的最大的搜索二叉树的头节点

是否是完全二叉树

最低公共祖先

判断二叉树是否是满二叉树

判断二叉树是不是搜索二叉树