二叉树算法题

经典二叉树算法题分析

树的问题就永远逃不开树的递归遍历框架这几行破代码:

/* 二叉树遍历框架 */
void traverse(TreeNode root) {
    // 前序遍历
    traverse(root.left)
    // 中序遍历
    traverse(root.right)
    // 后序遍历
}

比如: 快速排序就是个二叉树的前序遍历,归并排序就是个二叉树的后续遍历

写递归算法的关键是要明确函数的「定义」是什么,然后相信这个定义,利用这个定义推导最终结果,绝不要试图跳入递归

写树相关的算法,简单说就是,先搞清楚当前root节点该做什么,然后根据函数定义递归调用子节点,递归调用会让孩子节点做相同的事情

算法实践

翻转二叉树

// 将整棵树的节点翻转
TreeNode invertTree(TreeNode root) {
    // base case
    if (root == null) {
        return null;
    }

    /**** 前序遍历位置 ****/
    // root 节点需要交换它的左右子节点
    TreeNode tmp = root.left;
    root.left = root.right;
    root.right = tmp;

    // 让左右子节点继续翻转它们的子节点
    invertTree(root.left);
    invertTree(root.right);

    return root;
}

二叉树题目的一个难点就是,如何把题目的要求细化成每个节点需要做的事情。这种洞察力需要多刷题训练.

填充二叉树节点的右侧指针

(leetcode 116)给定一个 完美二叉树 ,其所有叶子节点都在同一层,每个父节点都有两个子节点。二叉树定义如下:

struct Node { int val; Node *left; Node *right; Node *next; } 填充它的每个 next 指针,让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点,则将 next 指针设置为 NULL。

初始状态下,所有 next 指针都被设置为 NULL。

进阶:

你只能使用常量级额外空间。 使用递归解题也符合要求,本题中递归程序占用的栈空间不算做额外的空间复杂度。

分析:

我们可以模仿上一道题,写出如下代码:

Node connect(Node root) {
    if (root == null || root.left == null) {
        return root;
    }

    root.left.next = root.right;

    connect(root.left);
    connect(root.right);

    return root;
}

这样有很大问题,因为没办法连接「跨父节点」的两个相邻节点。

仔细观察connect的定义,发现是链接参数的左右孩子节点,因此无法链接无共同父节点的两个节点。

那么,我们的做法就是增加函数参数,一个节点做不到,我们就给他安排两个节点,「将每一层二叉树节点连接起来」可以细化成「将每两个相邻节点都连接起来」:

// 主函数
Node connect(Node root) {
    if (root == null) return null;
    connectTwoNode(root.left, root.right);
    return root;
}

// 定义:输入两个节点,将它俩连接起来
void connectTwoNode(Node node1, Node node2) {
    if (node1 == null || node2 == null) {
        return;
    }
    /**** 前序遍历位置 ****/
    // 将传入的两个节点连接
    node1.next = node2;

    // 连接相同父节点的两个子节点
    connectTwoNode(node1.left, node1.right);
    connectTwoNode(node2.left, node2.right);
    // 连接跨越父节点的两个子节点
    connectTwoNode(node1.right, node2.left);
}

这样,connectTwoNode函数不断递归,可以无死角覆盖整棵二叉树,将所有相邻节点都连接起来,也就避免了我们之前出现的问题,这道题就解决了。

仔细观察connectTwoNode的定义,发现他是链接两个相邻节点,包含无共同父节点的两个节点,因此可以覆盖整棵树

将二叉树展开为链表(leetcode 114)

函数签名如下:

void flatten(TreeNode root);

我们尝试给出这个函数的定义:

flatten函数输入一个节点root,那么以root为根的二叉树就会被拉平为一条链表

我们再梳理一下,如何按题目要求把一棵树拉平成一条链表?很简单,以下流程:

1、将root的左子树和右子树拉平。

2、将root的右子树接到左子树下方,然后将整个左子树作为右子树。

// 定义:将以 root 为根的树拉平为链表
void flatten(TreeNode root) {
    // base case
    if (root == null) return;

    flatten(root.left);
    flatten(root.right);

    /**** 后序遍历位置 ****/
    // 1、左右子树已经被拉平成一条链表
    TreeNode left = root.left;
    TreeNode right = root.right;

    // 2、将左子树作为右子树
    root.left = null;
    root.right = left;

    // 3、将原先的右子树接到当前右子树的末端
    TreeNode p = root;
    while (p.right != null) {
        p = p.right;
    }
    p.right = right;
}

你看,这就是递归的魅力,你说flatten函数是怎么把左右子树拉平的?不容易说清楚,但是只要知道flatten的定义如此,相信这个定义,让root做它该做的事情,然后flatten函数就会按照定义工作。

构造最大二叉树(leetcode 654)

给定一个不含重复元素的整数数组 nums 。一个以此数组直接递归构建的 最大二叉树 定义如下:

二叉树的根是数组 nums 中的最大元素。 左子树是通过数组中 最大值左边部分 递归构造出的最大二叉树。 右子树是通过数组中 最大值右边部分 递归构造出的最大二叉树。 返回给定数组 nums 构建的 最大二叉树 。

/* 主函数 */
TreeNode constructMaximumBinaryTree(int[] nums) {
    return build(nums, 0, nums.length - 1);
}

/* 将 nums[lo..hi] 构造成符合条件的树,返回根节点 */
TreeNode build(int[] nums, int lo, int hi) {
    // base case
    if (lo > hi) {
        return null;
    }

    // 找到数组中的最大值和对应的索引
    int index = -1, maxVal = Integer.MIN_VALUE;
    for (int i = lo; i <= hi; i++) {
        if (maxVal < nums[i]) {
            index = i;
            maxVal = nums[i];
        }
    }

    TreeNode root = new TreeNode(maxVal);
    // 递归调用构造左右子树
    root.left = build(nums, lo, index - 1);
    root.right = build(nums, index + 1, hi);

    return root;
}

通过前序和中序遍历结果构造二叉树

输入某二叉树的前序遍历和中序遍历的结果,请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

分析,根据以下两幅图片,可以得到递归函数:

图片

图片

/* 主函数 */
TreeNode buildTree(int[] preorder, int[] inorder) {
    return build(preorder, 0, preorder.length - 1,
                 inorder, 0, inorder.length - 1);
}

TreeNode build(int[] preorder, int preStart, int preEnd, 
               int[] inorder, int inStart, int inEnd) {

    if (preStart > preEnd) {
        return null;
    }

    // root 节点对应的值就是前序遍历数组的第一个元素
    int rootVal = preorder[preStart];
    // rootVal 在中序遍历数组中的索引
    int index = 0;
    for (int i = inStart; i <= inEnd; i++) {
        if (inorder[i] == rootVal) {
            index = i;
            break;
        }
    }

    int leftSize = index - inStart;

    // 先构造出当前根节点
    TreeNode root = new TreeNode(rootVal);
    // 递归构造左右子树
    root.left = build(preorder, preStart + 1, preStart + leftSize,
                      inorder, inStart, index - 1);

    root.right = build(preorder, preStart + leftSize + 1, preEnd,
                       inorder, index + 1, inEnd);
    return root;
}

通过后序和中序遍历结果构造二叉树

原理同上,看下图:

图片

TreeNode build(int[] inorder, int inStart, int inEnd,
               int[] postorder, int postStart, int postEnd) {

    if (inStart > inEnd) {
        return null;
    }
    // root 节点对应的值就是后序遍历数组的最后一个元素
    int rootVal = postorder[postEnd];
    // rootVal 在中序遍历数组中的索引
    int index = 0;
    for (int i = inStart; i <= inEnd; i++) {
        if (inorder[i] == rootVal) {
            index = i;
            break;
        }
    }
    // 左子树的节点个数
    int leftSize = index - inStart;
    TreeNode root = new TreeNode(rootVal);
    // 递归构造左右子树
    root.left = build(inorder, inStart, index - 1,
                        postorder, postStart, postStart + leftSize - 1);

    root.right = build(inorder, index + 1, inEnd,
                        postorder, postStart + leftSize, postEnd - 1);
    return root;
}

做二叉树的问题,关键是把题目的要求细化,搞清楚根节点应该做什么,然后剩下的事情抛给前/中/后序的遍历框架就行了

寻找重复子树(leetcode 652)

判断使用前序,中序还是后续?

给定一棵二叉树,返回所有重复的子树。对于同一类的重复子树,你只需要返回其中任意一棵的根结点即可。

两棵树重复是指它们具有相同的结构以及相同的结点值。

分析:

这题咋做呢?还是老套路,先思考,对于某一个节点,它应该做什么

如果你想知道以自己为根的子树是不是重复的,是否应该被加入结果列表中,你需要知道什么信息?

你需要知道以下两点

1、以我为根的这棵二叉树(子树)长啥样

2、以其他节点为根的子树都长啥样

好,那我们一个一个来解决,先来思考,我如何才能知道以自己为根的二叉树长啥样

其实看到这个问题,就可以判断本题要使用「后序遍历」框架来解决:

void traverse(TreeNode root) {
    traverse(root.left);
    traverse(root.right);
    /* 解法代码的位置 */
}

为什么?很简单呀,我要知道以自己为根的子树长啥样,是不是得先知道我的左右子树长啥样,再加上自己,就构成了整棵子树的样子?

现在,明确了要用后序遍历,那应该怎么描述一棵二叉树的模样呢?可以通过拼接字符串的方式把二叉树序列化,看下代码:

String traverse(TreeNode root) {
    // 对于空节点,可以用一个特殊字符表示
    if (root == null) {
        return "#";
    }
    // 将左右子树序列化成字符串
    String left = traverse(root.left);
    String right = traverse(root.right);
    /* 后序遍历代码位置 */
    // 左右子树加上自己,就是以自己为根的二叉树序列化结果
    String subTree = left + "," + right + "," + root.val;
    return subTree;
}

这样,我们第一个问题就解决了,对于每个节点,递归函数中的subTree变量就可以描述以该节点为根的二叉树

现在我们解决第二个问题,我知道了自己长啥样,怎么知道别人长啥样?这样我才能知道有没有其他子树跟我重复对吧。

这很简单呀,我们借助一个外部数据结构,让每个节点把自己子树的序列化结果存进去,这样,对于每个节点,不就可以知道有没有其他节点的子树和自己重复了么?

初步思路可以使用HashSet记录子树,代码如下:

// 记录所有子树
HashSet<String> memo = new HashSet<>();
// 记录重复的子树根节点
LinkedList<TreeNode> res = new LinkedList<>();

String traverse(TreeNode root) {
    if (root == null) {
        return "#";
    }

    String left = traverse(root.left);
    String right = traverse(root.right);

    String subTree = left + "," + right+ "," + root.val;

    if (memo.contains(subTree)) {
        // 有人和我重复,把自己加入结果列表
        res.add(root);
    } else {
        // 暂时没人跟我重复,把自己加入集合
        memo.add(subTree);
    }
    return subTree;
}

但是呢,这有个问题,如果出现多棵重复的子树,结果集res中必然出现重复,而题目要求不希望出现重复。

为了解决这个问题,可以把HashSet升级成HashMap,额外记录每棵子树的出现次数:

// 记录所有子树以及出现的次数
HashMap<String, Integer> memo = new HashMap<>();
// 记录重复的子树根节点
LinkedList<TreeNode> res = new LinkedList<>();

/* 主函数 */
List<TreeNode> findDuplicateSubtrees(TreeNode root) {
    traverse(root);
    return res;
}

/* 辅助函数 */
String traverse(TreeNode root) {
    if (root == null) {
        return "#";
    }

    String left = traverse(root.left);
    String right = traverse(root.right);

    String subTree = left + "," + right+ "," + root.val;

    int freq = memo.getOrDefault(subTree, 0);
    // 多次重复也只会被加入结果集一次
    if (freq == 1) {
        res.add(root);
    }
    // 给子树对应的出现次数加一
    memo.put(subTree, freq + 1);
    return subTree;
}