LeetCode刷题日记之二叉树（四）

前言

又是学习LeetCode二叉树部分内容的新一天，希望博主记录的内容能够对大家有所帮助 ，一起加油吧朋友们！💪💪💪

从中序和后序遍历序列构造二叉树

LeetCode题目链接

给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗二叉树。

我们先来梳理一下构造逻辑🤔🤔🤔

1. 首先是后序遍历的整数数组的顺序是：左子树->右子树->根节点，所以后序遍历的最后一个元素一定是树的根节点。而中序遍历的顺序则是：左子树->根节点->右子树，所以通过中序遍历如果确定了根节点的位置则就能确定左子树和右子树的边界。
2. 递归的过程：我们先从后序数组获取当前子树的根节点（最后一个元素），然后在中序遍历中根据根节点将inorder划分为左子树和右子树，接着递归构建左子树和右子树并返回构建好的子树根节点。

接下来我们来梳理递归三要素：

• 确定递归的参数和返回值

//递归处理时需要递归处理的中序数组和后序数组，这里实际上有三种方法🤔
//第一种方法：参数只有中序数组和后序数组，这会使得每次递归的时候都要构建两个中后序数组，效率极低🤔
//第二种方法：参数为原始中序数组和后序数组，加上中序开始结束索引和后序开始结束索引🤔
//第三种方法：只传索引，将原始中序数组和后序数组作为全局变量，但规模大的问题全局变量还是不推荐🤔
//综上我们选取第二种参数设置方法并返回构建好的二叉树的根节点
private TreeNode build(int[] inorder, int[] postorder, int inStart, int inEnd, int postStart, int postEnd){}

• 确定递归的出口

//递归处理的的出口即索引inStart > inEnd和postStart > postEnd，这表明已经没有节点来构建树了🤔
if(inStart > inEnd && postStart > postEnd){
    return null;
}

• 确定递归的单层处理逻辑

//首先获取后序数组的根节点的值，构建根节点
int rootVal = postorder[postEnd];
TreeNode root = new TreeNode(rootVal);

//在中序数组中找到根节点，因为每次递归都要进行索引搜索，所以我们用哈希表提前存储索引来提高查询效率
int rootIndex = inorderIndexMap.get(rootVal);

//递归构建左子树和右子树
int leftTreeSize = rootIndex - inStart; // 左子树的大小
root.left = build(inorder, postorder, inStart, rootIndex - 1, postStart, postStart + leftTreeSize - 1);
root.right = build(inorder, postorder, rootIndex + 1, inEnd, postStart +leftTreeSize, postEnd - 1);

//构建完毕返回根节点
return root;

逻辑很清晰的梳理完毕，完整代码如下：

class Solution {
    private HashMap<Integer, Integer> inorderIndexMap; //存储中序遍历的
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        //构建中序遍历的索引哈希表
        inorderIndexMap = new HashMap<>();
        for(int i = 0; i < inorder.length; i++){
            inorderIndexMap.put(inorder[i], i);
        }
        return build(inorder, postorder, 0, inorder.length - 1, 0, postorder.length - 1);
    }

    private TreeNode build(int[] inorder, int[] postorder, int inStart, int inEnd, int postStart, int postEnd){
        if(inStart > inEnd && postStart > postEnd){ //递归出口
            return null;
        }

        //首先获取后序数组的根节点的值，构建根节点
        int rootVal = postorder[postEnd];
        TreeNode root = new TreeNode(rootVal);

        //在中序数组中找到根节点，因为每次递归都要进行索引搜索，所以我们用哈希表提前存储索引来提高查询效率
        int rootIndex = inorderIndexMap.get(rootVal);

        //递归构建左子树和右子树
        int leftTreeSize = rootIndex - inStart; // 左子树的大小
        root.left = build(inorder, postorder, inStart, rootIndex - 1, postStart, postStart + leftTreeSize - 1);
        root.right = build(inorder, postorder, rootIndex + 1, inEnd, postStart +leftTreeSize, postEnd - 1);

        //构建完毕返回根节点
        return root;
    }
}

对了，另外的话我们来每日一练树节点定义的吧✊，因为LeetCode里都是预先定义好的

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;
	}
}

从前序和中序遍历序列

LeetCode题目链接

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

与上题逻辑一样，把后序数组的处理逻辑换成前序数组即可。🤔🤔🤔这里博主就直接给出完整代码了，有不清楚的地方建议再把上述的分析内容多看几遍🤝🤝🤝

class Solution {
    private HashMap<Integer, Integer> inorderIndexMap = new HashMap<>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        // 构建中序遍历的索引哈希表
        for(int i = 0; i < inorder.length; i++){
            inorderIndexMap.put(inorder[i], i);
        }
        return build(inorder, preorder, 0, inorder.length - 1, 0, preorder.length - 1);
    }

    private TreeNode build(int[] inorder, int[] preorder, int inStart, int inEnd, int preStart, int preEnd){
        if(inStart > inEnd && preStart > preEnd){return null;} // 递归出口

        //获取前序遍历的根节点
        int rootVal = preorder[preStart];

        //找到根节点在中序遍历中的位置
        TreeNode root = new TreeNode(rootVal);
        int rootIndex = inorderIndexMap.get(rootVal);

        //递归生成左子树和右子树
        int leftTreeSize = rootIndex -inStart;
        root.left = build(inorder, preorder, inStart, rootIndex - 1, preStart + 1, preStart + leftTreeSize - 1);
        root.right = build(inorder, preorder, rootIndex + 1, inEnd, preStart + leftTreeSize + 1, preEnd);

        return root;
    }
}

完成了这两道题的话，另外需要知道的是前序和后序是不能唯一确定一颗二叉树的，因为没有中序无法确定左右部分。🤔🤔🤔

最大二叉树

给定一个不重复的整数数组 nums 。 最大二叉树可以用下面的算法从 nums 递归地构建:

1. 用 nums 中的最大值创建一个根节点
2. 递归地在最大值左边的子数组前缀上构建左子树
3. 递归地在最大值 右边的子数组后缀上构建右子树

我们来梳理一下思路🤔🤔🤔：

• 首先是确定根节点，根节点是数组的最大值，可以通过遍历数组来找最大值
• 然后的递归构建子树，用最大值左边的子数组构建左子树，右边的子数组构建右子树
• 当数组为空或子数组的边界交错时，返回null表示已经没有节点可以构建了

接着我们来梳理递归三要素

• 确定递归的参数和返回值

//构建数组的话需要传入数组和左右边界
//返回值则是所构建树的根节点
private TreeNode constructTree(int[] nums, int left, int right){}

• 确定递归的出口

//边界重叠返回null表示无节点可构建了
if(left > right) return null;

• 确定递归的单层处理逻辑

//找到当前子数组的最大值和索引
int maxIndex = left;
for(int i = left; i <= right; i++){
    if(nums[i] > nums[maxIndex]) maxIndex = i;
}
//找到后创建根节点并递归构建左右子树
TreeNode root = new TreeNode(nums[maxIndex]);
root.left = constructTree(nums, left, maxIndex - 1);
root.right = constructTree(nums, maxIndex + 1, right);

//返回树的根节点
return root;

完整代码如下：

class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return constructTree(nums, 0, nums.length - 1);
    }
    private TreeNode constructTree(int[] nums, int left, int right){
        if(left > right) return null; // 递归出口

        //边界重叠返回null表示无节点可构建了
        if(left > right) return null;

        //找到当前子数组的最大值和索引
        int maxIndex = left;
        for(int i = left; i <= right; i++){
            if(nums[i] > nums[maxIndex]) maxIndex = i;
        }
        //找到后创建根节点并递归构建左右子树
        TreeNode root = new TreeNode(nums[maxIndex]);
        root.left = constructTree(nums, left, maxIndex - 1);
        root.right = constructTree(nums, maxIndex + 1, right);

        //返回树的根节点
        return root;
    }
}

合并二叉树

LeetCode题目链接

两颗二叉树 root1 和 root2 ，将两颗二叉树进行覆盖叠加，重叠的节点值相加作为合并后节点的值，不然不为null的节点直接作为新二叉树的节点

我们来梳理一下思路🤔🤔🤔

• 节点重叠的处理：如果两个节点都存在则合并这两个节点的值，如果一个节点存在而另一个节点不存在，则直接只用存在的节点作为新树的节点
• 递归合并左右子树

这道题递归的思路还是比较简单的，我们进一步来梳理递归三要素：

• 确定递归的参数和返回值

//参数只需两个树的根节点，然后返回合并后的树的根节点
private TreeNode mergeTrees(TreeNode root1, TreeNode root2){}

• 确定递归的出口

if(root1 == null) return root2; //如果根节点1为空则返回根节点2
if(root2 == null) return root1; //如果根节点2为空则返回根节点1

• 确定递归的单层处理逻辑

//创建一个新节点来合并节点值
TreeNode mergedNode = new TreeNode(root1.val + root2.val);

//递归合并左右子树
mergedNode.left = mergeTrees(root1.left, root2.left);
mergedNode.right = mergeTrees(root1.right, root2.right);

//返回合并树的根节点
return mergedNode;

完整代码如下：

class Solution {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if(root1 == null) return root2; //如果根节点1为空则返回根节点2
        if(root2 == null) return root1; //如果根节点2为空则返回根节点1

        //创建一个新节点来合并节点值
        TreeNode mergedNode = new TreeNode(root1.val + root2.val);

        //递归合并左右子树
        mergedNode.left = mergeTrees(root1.left, root2.left);
        mergedNode.right = mergeTrees(root1.right, root2.right);

        //返回合并树的根节点
        return mergedNode;
    }
}

我们接着来梳理一下迭代法的思路

• 使用队列处理节点：我们使用队列来存储当前合并节点及其来自两棵树的节点🤔
• 正确设置左右子树：对于每一个合并的节点，如果其中树的节点存在，直接添加值，否则直接连接保留结构。

/**迭代法 */
class Solution {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
       // 如果两棵树都为空，返回null
        if (root1 == null && root2 == null) return null;
        
        // 使用栈来进行迭代
        Stack<TreeNode[]> stack = new Stack<>();
        TreeNode mergedRoot = new TreeNode(); // 创建一个虚拟根节点
        stack.push(new TreeNode[] {mergedRoot, root1, root2});

        while (!stack.isEmpty()) {
            TreeNode[] nodes = stack.pop();
            TreeNode mergedNode = nodes[0]; // 当前合并的节点
            TreeNode node1 = nodes[1]; // 来自树1的节点
            TreeNode node2 = nodes[2]; // 来自树2的节点

            // 如果节点都存在，合并他们的值
            if (node1 != null && node2 != null) {
                mergedNode.val = node1.val + node2.val;
                mergedNode.left = new TreeNode(); // 创建左子树的虚拟节点
                mergedNode.right = new TreeNode(); // 创建右子树的虚拟节点
                // 将左子树和右子树加入栈，继续合并
                stack.push(new TreeNode[] {mergedNode.left, node1.left, node2.left});
                stack.push(new TreeNode[] {mergedNode.right, node1.right, node2.right});
            } else if (node1 != null) {
                // 如果树1的节点存在，直接赋值
                mergedNode.val = node1.val;
            } else if (node2 != null) {
                // 如果树2的节点存在，直接赋值
                mergedNode.val = node2.val;
            }
        }

        return mergedRoot; // 返回合并后的根节点
    }
}

这段代码存在了一个问题，就是当要合并的左右节点它们各自的左节点和右节点为空就不该构建新节点去进行递归合并的🤔🤔

所以我们在递归前进行一个判断

/**迭代法 */
class Solution {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
       // 如果两棵树都为空，返回null
        if (root1 == null && root2 == null) return null;

        // 使用栈来进行迭代
        Stack<TreeNode[]> stack = new Stack<>();
        TreeNode mergedRoot = new TreeNode(0); // 虚拟根节点
        stack.push(new TreeNode[] {mergedRoot, root1, root2});

        while (!stack.isEmpty()) {
            TreeNode[] nodes = stack.pop();
            TreeNode mergedNode = nodes[0]; // 当前合并的节点
            TreeNode node1 = nodes[1]; // 来自树1的节点
            TreeNode node2 = nodes[2]; // 来自树2的节点

            // 如果两个节点都存在，合并他们的值
            if (node1 != null && node2 != null) {
                mergedNode.val = node1.val + node2.val;

                // 推入左子树和右子树，注意确保非空节点才创建新节点🤔🤔
                if (node1.left != null || node2.left != null) {
                    mergedNode.left = new TreeNode(); // 创建左子树的虚拟节点
                    stack.push(new TreeNode[] {mergedNode.left, node1.left, node2.left});
                }
                if (node1.right != null || node2.right != null) {
                    mergedNode.right = new TreeNode(); // 创建右子树的虚拟节点
                    stack.push(new TreeNode[] {mergedNode.right, node1.right, node2.right});
                }
            } else if (node1 != null) {
                // 如果树1的节点存在，直接赋值
                mergedNode.val = node1.val;

                // 相同逻辑处理子节点🤔🤔
                if (node1.left != null || node1.right != null) {
                    if (node1.left != null) {
                        mergedNode.left = new TreeNode(); // 左子树
                        stack.push(new TreeNode[] {mergedNode.left, node1.left, null});
                    }
                    if (node1.right != null) {
                        mergedNode.right = new TreeNode(); // 右子树
                        stack.push(new TreeNode[] {mergedNode.right, node1.right, null});
                    }
                }
            } else if (node2 != null) {
                // 如果树2的节点存在，直接赋值
                mergedNode.val = node2.val;

                //相同逻辑处理子节点🤔🤔
                if (node2.left != null || node2.right != null) {
                    if (node2.left != null) {
                        mergedNode.left = new TreeNode(); // 左子树
                        stack.push(new TreeNode[] {mergedNode.left, null, node2.left});
                    }
                    if (node2.right != null) {
                        mergedNode.right = new TreeNode(); // 右子树
                        stack.push(new TreeNode[] {mergedNode.right, null, node2.right});
                    }
                }
            }
        }

        return mergedRoot; // 返回合并后的根节点
    }
}

总结

今天的内容就分享到这儿了，国庆假期快要来了，提前祝大家国庆快乐🎉🎉🎉