当前位置： 首页 > news >正文

LeetCode精选200道--二叉树篇（二）

news 来源：原创 2024/4/30 1:38:13

二叉树篇（二）

  • 前言
  • 完全二叉树的节点个数
    • 普通二叉树逻辑
      • 递归
    • 完全二叉树逻辑
  • 平衡二叉树
    • 题外话
    • 递归
  • 二叉树的所有路径
    • 思路
    • 递归
  • 相同的树
    • 100. 相同的树
  • 另一棵树的子树
  • 左叶子之和
    • 思路
  • 找树左下角的值
    • 思路
  • 112. 路径总和
    • 思路
  • 106. 从中序与后序遍历序列构造二叉树
    • 根据中序和后序遍历结果还原二叉树
    • 树的还原过程描述
    • 树的还原过程变量定义
    • 位置关系的计算
  • 105.从前序与中序遍历序列构造二叉树
  • 前序与后序遍历序列能构造二叉树吗？
  • 654. 最大二叉树
    • 思路

前言

参考：https://www.programmercarl.com/

完全二叉树的节点个数

image-20220820114439490

普通二叉树逻辑

递归

class Solution {
    public int getNodesNum(TreeNode root){
        if(root == null) return 0;
        int leftNum = countNodes(root.left);
        int rightNum = countNodes(root.right);
        int treeNum = leftNum + rightNum + 1;      // 中
        return treeNum;

    }

    public int countNodes(TreeNode root) {
        return getNodesNum(root);
    }
}

精简版

class Solution {
    public int countNodes(TreeNode root) {
		if(root == null) return 0;
		return 1 + countNodes(root.left) + countNodes(root.right)
    }
}

完全二叉树逻辑

完全二叉树只有两种情况，情况一：就是满二叉树，情况二：最后一层叶子节点没有满。

对于情况一，可以直接用 2^树深度 - 1 来计算，注意这里根节点深度为1。

对于情况二，分别递归左孩子，和右孩子，递归到某一深度一定会有左孩子或者右孩子为满二叉树，然后依然可以按照情况1来计算。

完全二叉树（一）如图：

222.完全二叉树的节点个数

完全二叉树（二）如图：

222.完全二叉树的节点个数1

可以看出如果整个树不是满二叉树，就递归其左右孩子，直到遇到满二叉树为止，用公式计算这个子树（满二叉树）的节点数量。

只有去画图，然后不断的理解

image-20220821103248691

    public int countNodes(TreeNode root) {
        if (root == null) return 0;
        TreeNode left = root.left;
        TreeNode right = root.right;
        int leftHeight = 0, rightHeight = 0;
        while (left != null) {
            left = left.left;
            leftHeight++;
        }
        while (right != null) {
            right = right.right;
            rightHeight++;
        }
        if (leftHeight == rightHeight) {
            //其中(2^leftDepth - 1) + 1 为左子树+根节点。简写就是2^leftDepth
            return (2 << leftHeight) - 1;
        }
        return countNodes(root.left) + countNodes(root.right) + 1;
    }

平衡二叉树

image-20220821103340631

题外话

这里强调一波概念：

  • 二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数。
  • 二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数。

但leetcode中强调的深度和高度很明显是按照节点来计算的，如图：

110.平衡二叉树2关于根节点的深度究竟是1 还是 0，不同的地方有不一样的标准，leetcode的题目中都是以节点为一度，即根节点深度是1。但维基百科上定义用边为一度，即根节点的深度是0，我们暂时以leetcode为准（毕竟要在这上面刷题)。

因为求深度可以从上到下去查 所以需要前序遍历（中左右），而高度只能从下到上去查，所以只能后序遍历（左右中）

那是因为代码的逻辑其实是求的根节点的高度，而根节点的高度就是这棵树的最大深度，所以才可以使用后序遍历。

递归

递归三步曲分析：

  1. 明确递归函数的参数和返回值

参数：当前传入节点。
返回值：以当前传入节点为根节点的树的高度。

那么如何标记左右子树是否差值大于1呢？

如果当前传入节点为根节点的二叉树已经不是二叉平衡树了，还返回高度的话就没有意义了。

所以如果已经不是二叉平衡树了，可以返回-1 来标记已经不符合平衡树的规则了。

代码如下：

int getHeight(TreeNode node)

  1. 明确终止条件

    递归的过程中依然是遇到空节点了为终止，返回0，表示当前节点为根节点的树高度为0

    代码如下：

    if (node == NULL) {
    return 0;
}

  2. 单层递归的逻辑

如何判断以当前传入节点为根节点的二叉树是否是平衡二叉树呢？当然是其左子树高度和其右子树高度的差值。

分别求出其左右子树的高度，然后如果差值小于等于1，则返回当前二叉树的高度，否则则返回-1，表示已经不是二叉平衡树了。

int leftHeight = getHeight(node.left); // 左
if (leftHeight == -1) return -1;
int rightHeight = getHeight(node.right); // 右
if (rightHeight == -1) return -1;

int result;
if (abs(leftHeight - rightHeight) > 1) {  // 中
    result = -1;
} else {
    result = 1 + max(leftHeight, rightHeight); // 以当前节点为根节点的树的最大高度
}

return result;

代码精简之后如下：

int leftHeight = getHeight(node.left); // 左
if (leftHeight == -1) return -1;
int rightHeight = getHeight(node.right); // 右
if (rightHeight == -1) return -1;

return abs(leftHeight - rightHeight) > 1 ? -1 : 1 + max(leftHeight, rightHeight);

此时递归的函数就已经写出来了，这个递归的函数传入节点指针，返回以该节点为根节点的二叉树的高度，如果不是二叉平衡树，则返回-1。

最后本题整体递归代码如下：

多递归不理解的，可以画图去模拟节点的状态！

image-20220822155922422

class Solution {
    /**
     * 递归法
     */
    public boolean isBalanced(TreeNode root) {
        return getHeight(root) != -1;
    }

    private int getHeight(TreeNode root) {
        if(root == null) return 0;

        int leftHeight = getHeight(root.left); // 左
        if (leftHeight == -1) return -1;
        int rightHeight = getHeight(root.right); // 右
        if (rightHeight == -1) return -1;

        int result;
        if (Math.abs(leftHeight - rightHeight) > 1) {  // 中
            result = -1;
        } else {
            result = 1 + Math.max(leftHeight, rightHeight); // 以当前节点为根节点的树的最大高度
        }

        return result;
    }

}

简化：

class Solution {
    boolean isBalanced(TreeNode root) {
        return getHeight(root) == -1 ? false : true;
    }
    // 返回以该节点为根节点的二叉树的高度，如果不是平衡二叉树了则返回-1
    public int getHeight(TreeNode root) {
        if(root == null) return 0;
        int leftHeight = getHeight(root.left);
        if(leftHeight == -1) return -1;
        int rightHeight = getHeight(root.right);
        if(rightHeight == -1) return -1;
        return Math.abs(leftHeight - rightHeight) > 1 ? -1 : 1 + Math.max(leftHeight,rightHeight);
    }
};

二叉树的所有路径

image-20220822160558713

思路

这道题目要求从根节点到叶子的路径，所以需要前序遍历，这样才方便让父节点指向孩子节点，找到对应的路径。

在这道题目中将第一次涉及到回溯，因为我们要把路径记录下来，需要回溯来回退一个路径在进入另一个路径。

前序遍历以及回溯的过程如图：

257.二叉树的所有路径

我们先使用递归的方式，来做前序遍历。要知道递归和回溯就是一家的，本题也需要回溯。

递归

  1. 递归函数函数参数以及返回值

要传入根节点，记录每一条路径的path，和存放结果集的result，这里递归不需要返回值，代码如下：

void traversal(TreeNode cur, ArrayList<Integer> path, ArrayList<String> result)
  1. 确定递归终止条件

再写递归的时候都习惯了这么写

if (cur == NULL) {
    终止处理逻辑
}

但是本题的终止条件这样写会很麻烦，因为本题要找到叶子节点，就开始结束的处理逻辑了（把路径放进result里）。

那么什么时候算是找到了叶子节点？ 是当 cur不为空，其左右孩子都为空的时候，就找到叶子节点。

所以本题的终止条件是：

if (cur->left == NULL && cur->right == NULL) {
    终止处理逻辑
}

为什么没有判断cur是否为空呢，因为下面的逻辑可以控制空节点不入循环。

再来看一下终止处理的逻辑。

通过StringBuilder来拼接paths集合里记录的节点的值，最后将StringBuilder转换为Stgring即可

  1. 确定单层递归逻辑

因为是前序遍历，需要先处理中间节点，中间节点就是我们要记录路径上的节点，先放进paths中。

paths.add(root.val);//把节点的值加到path集合

然后是递归和回溯的过程，上面说过没有判断cur是否为空，那么在这里递归的时候，如果为空就不进行下一层递归了。

所以递归前要加上判断语句，下面要递归的节点是否为空，如下

if (root.left != null) {}

if (root.right != null) {}

此时还没完，递归完，要做回溯啊，因为path 不能一直加入节点，它还要删节点，然后才能加入新的节点。

回溯和递归是一一对应的，有一个递归，就要有一个回溯

if (root.left != null) {
traversal(root.left, paths, res);
paths.remove(paths.size() - 1);// 回溯，相当于把第一个路径得到的结果删除，还原paths集合
}
if (root.right != null) {
traversal(root.right, paths, res);
paths.remove(paths.size() - 1);// 回溯，同上
}

class Solution {
    /**
     * 递归法
     */
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> res = new ArrayList<>();//存放具体的路径
        if (root == null) {
            return res;
        }
        List<Integer> paths = new ArrayList<>();//路径中存放节点的值
        traversal(root, paths, res);
        return res;
    }

    private void traversal(TreeNode root, List<Integer> paths, List<String> res) {
        paths.add(root.val);//把节点的值加到path集合
        // 叶子结点
        if (root.left == null && root.right == null) {//如果某个节点的左右节点都为空那说明它就是叶子节点
            // 输出
            StringBuilder sb = new StringBuilder(); //线程不安全，用来拼接字符串方便

            //如果到了叶子结点才开始遍历paths集合中元素，将他们拼接成字符串，最后一个元素不拼接
            //因为最后一个拼接的话，还会加上->,所以最后一个元素放到最后拼接
            for (int i = 0; i < paths.size() - 1; i++) {
                sb.append(paths.get(i)).append("->");
            }

            sb.append(paths.get(paths.size() - 1));//拼接最后一个元素
            res.add(sb.toString());//转化为字符出
            return;
        }
        if (root.left != null) {
            traversal(root.left, paths, res);
            paths.remove(paths.size() - 1);// 回溯，相当于把第一个路径得到的结果删除，还原paths集合
        }
        if (root.right != null) {
            traversal(root.right, paths, res);
            paths.remove(paths.size() - 1);// 回溯，同上
        }
    }
}

相同的树

100. 相同的树

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        return compare(p,q);
    }

    //1.确定递归的返回值和参数
    public boolean compare(TreeNode p, TreeNode q){
        //2.确定递归的终止条件
        if(p == null && q != null) return false;
        if(p != null && q == null) return false;
        if(p == null && q == null) return true;
        if(p.val != q.val) return false;
        //3.确定单层递归的逻辑
        boolean compareLeft = compare(p.left,q.left);
        boolean compareRight = compare(p.right,q.right);
        return compareRight && compareLeft;
    }
}

另一棵树的子树

572. 另一棵树的子树

给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。

二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。

image-20220823113919809

image-20220823113952645

/**
 * Definition for a binary tree node.
 * 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;
 *     }
 * }
 */
class Solution {
    /**
    * 判断两树是否相等
    * @param l
    * @param r
    * @return
    */
    private boolean isEqual(TreeNode l, TreeNode r){
        if(l == null && r == null) return true;//两树均空自然相等
        if(l == null || r == null) return false;//一空一非空，自然不等
        if(l.val == r.val)//递归判断
            return isEqual(l.left,r.left) && isEqual(l.right,r.right);
        return false;
    }

    /**
    * 判断 t 树是否是 s 树的子树
    * @param s
    * @param t
    * @return
    */
    public boolean isSubtree(TreeNode s, TreeNode t) {
        if(s == null && t == null)
            return true;
        if(s == null || t == null) return false;
        if(s.val == t.val){
            return isEqual(s,t) || isSubtree(s.left, t) || isSubtree(s.right, t);
        }
        // 根节点不同，那么就不同考虑s和t相等的情形了
        return isSubtree(s.left, t) || isSubtree(s.right, t);
    }
}

左叶子之和

image-20220824094840062

思路

class Solution {
    //1.因为最后的返回结果就是int，所以直接用这个函数即可
    public int sumOfLeftLeaves(TreeNode root) {
        //2.确定递归结束条件
        if(root == null) return 0;
        //3.确定单层递归逻辑，后序遍历
        int leftValue = sumOfLeftLeaves(root.left);
        int rightValue = sumOfLeftLeaves(root.right);

        int midValue = 0;
        //这里判断开始计算，只有当某个结点的左结点不为空的情况，并且这个结点没有左右结点才开始计算它的值
        if(root.left != null && root.left.left == null && root.left.right == null){
            midValue = root.left.val;
        }
        int sum = midValue + leftValue + rightValue;
        return sum;
    }
}

找树左下角的值

image-20220824175055783

思路

根据前面的练习，我们一下就可以想到通过遍历，直到找到最左边的值返回就可以了呗。但是最然到最左边了，但是如何确保是最左边呢这其实就是说如何判断到最后一行了。

所以简化一下题目就是找到二叉树最后一行，最左边的值

递归三部曲：

  1. 确定递归函数的参数和返回值

参数必须有要遍历的树的根节点，还有就是一个int型的变量用来记录最长深度。 这里就不需要返回值了，所以递归函数的返回类型为void。

本题还需要类里的两个全局变量，maxLen用来记录最大深度，maxleftValue记录最大深度最左节点的数值。

代码如下：

int maxLen = INT_MIN;   // 全局变量 记录最大深度
int maxleftValue;       // 全局变量 最大深度最左节点的数值
void traversal(TreeNode root, int leftLen)

如果需要遍历整棵树，递归函数就不能有返回值。如果需要遍历某一条固定路线，递归函数就一定要有返回值！

  1. 确定终止条件

当遇到叶子节点的时候，就需要统计一下最大的深度了，所以需要遇到叶子节点来更新最大深度。

if (root.left == NULL && root.right == NULL) {
    if (leftLen > maxLen) {
        maxLen = leftLen;           // 更新最大深度
        maxleftValue = root->val;   // 最大深度最左面的数值
    }
    return;
}
  1. 确定单层递归的逻辑
//找到叶子结点
if(root.left == null && root.right == null){
    //判断最大深度
    if(deep > Deep) {
        value = root.val;
        Deep = deep;
    }
}
//前序遍历树
if(root.left != null) findLeftValue(root.left,deep + 1);
if(root.right != null) findLeftValue(root.right,deep + 1);

完整代码如下：

/**
 * Definition for a binary tree node.
 * 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;
 *     }
 * }
 */
 
/**
 * 题意：在树的最后一行找到最左边的值。
 */

class Solution {
    private int Deep = -1;
    private int value = 0;

    public int findBottomLeftValue(TreeNode root) {
        value = root.val;
        findLeftValue(root,0);
        return value;
    }

    public void findLeftValue(TreeNode root,int deep){
        if(root == null) return;
        if(root.left == null && root.right == null){
            if(deep > Deep) {
                value = root.val;
                Deep = deep;
            }
        }
        if(root.left != null) findLeftValue(root.left,deep + 1);
        if(root.right != null) findLeftValue(root.right,deep + 1);
    }
}

112. 路径总和

思路

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。

叶子节点 是指没有子节点的节点。

image-20220825110629670

image-20220825110944864

 /**
    由目标值减去遍历路上的值，直到遍历到叶子节点看结果是否等于0，等于0返回true，不等于返回false
  */
class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        //2.确定递归的结束条件
        if(root == null) return false;
        //3.确定递归的逻辑
        targetSum -= root.val;
        if(root.left == null && root.right == null){
            return targetSum == 0;
        }
        if(root.left != null){
            boolean left = hasPathSum(root.left,targetSum);
            if(left) return true;
        }
        if(root.right != null){
            boolean right = hasPathSum(root.right,targetSum);
            if(right) return true;
        }
        return false;

    }
}

106. 从中序与后序遍历序列构造二叉树

image-20220826095712610

根据中序和后序遍历结果还原二叉树

https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/solution/tu-jie-gou-zao-er-cha-shu-wei-wan-dai-xu-by-user72/

如何根据两个顺序构造一个唯一的二叉树？就是以后序数值的最后一个元素为切割点，先切中序数组，根据中序数组，反过来在切后续数组。一层层切下去，每次后序数组最后一个元素的就是结点元素

流程如图：

image-20220827111205941

树的还原过程描述

  • 首先在后序遍历序列中找到根节点(最后一个元素)
  • 根据根节点在中序遍历序列中找到根节点的位置
  • 根据根节点的位置将中序遍历序列分为左子树和右子树
  • 根据根节点的位置确定左子树和右子树在中序数组和后续数组中的左右边界位置
  • 递归构造左子树和右子树
  • 返回根节点结束

树的还原过程变量定义

需要定义几个变量帮助我们进行树的还原

  1. HashMap memo 需要一个哈希表来保存中序遍历序列中,元素和索引的位置关系.因为从后序序列中拿到根节点后，要在中序序列中查找对应的位置,从而将数组分为左子树和右子树
  2. int ri 根节点在中序遍历数组中的索引位置
  3. 中序遍历数组的两个位置标记 [is, ie]，is 是起始位置，ie 是结束位置
  4. 后序遍历数组的两个位置标记 [ps, pe] ps 是起始位置，pe 是结束位置

位置关系的计算

在找到根节点位置以后，我们要确定下一轮中，左子树和右子树在中序数组和后续数组中的左右边界的位置。

  1. 左子树-中序数组 is = is, ie = ri - 1
  2. 左子树-后序数组 ps = ps, pe = ps + ri - is - 1 (pe计算过程解释，后续数组的起始位置加上左子树长度-1 就是后后序数组结束位置了，左子树的长度 = 根节点索引-左子树)
  3. 右子树-中序数组 is = ri + 1, ie = ie
  4. 右子树-后序数组 ps = ps + ri - is, pe - 1。

image-20220828110151253

image-20220828110947791

代码如下：

class Solution {

    //定义hash表，用来保存中序数组结果
    HashMap<Integer,Integer> memo = new HashMap<>();
    //定义int数组用来保存后序遍历的结果
    int[] post;


    public TreeNode buildTree(int[] inorder, int[] postorder) {
        //遍历中序数组元素，并将它们保存在HashMap当中
        for(int i = 0;i< inorder.length;i++) memo.put(inorder[i], i);

        //后序数组的结果放在post数组中
        post = postorder;

        //调用递归函数构建二叉树
        TreeNode root = buildTree(0,inorder.length - 1, 0, post.length -1);
        return root;
    
    }

    public TreeNode buildTree(int inorderStart, int inorderEnd, int postStart, int postEnd) {
        //边界条件判断
        if(inorderEnd < inorderStart || postEnd < postStart) return null;

        //取出后序遍历数组中的最后一个元素
        int root = post[postEnd];

        //找出后序遍历数组中的最后一个元素在中序遍历Hash表中的key
        int index = memo.get(root);

        //生成二叉树
        TreeNode node = new TreeNode(root);

        //递归的逻辑
        //1.构建左子树
        node.left = buildTree(inorderStart, index -1, postStart, postStart + index - inorderStart - 1);
        //2.构建右子树
        node.right = buildTree(index + 1, inorderEnd, postStart + index - inorderStart,postEnd -1);

        return node;
    }
}

105.从前序与中序遍历序列构造二叉树

这个是找出前序数组中的第一个元素，然后切割

和106区别就在于一个是基于后序遍历数组进行切割的，一个是基于前序遍历的数据进行切割的

class Solution {
    Map<Integer, Integer> map;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        map = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) { // 用map保存中序序列的数值对应位置
            map.put(inorder[i], i);
        }

        return findNode(preorder, 0, preorder.length, inorder,  0, inorder.length);  // 前闭后开
    }

    public TreeNode findNode(int[] preorder, int preBegin, int preEnd, int[] inorder, int inBegin, int inEnd) {
        // 参数里的范围都是前闭后开
        if (preBegin >= preEnd || inBegin >= inEnd) {  // 不满足左闭右开，说明没有元素，返回空树
            return null;
        }
        int rootIndex = map.get(preorder[preBegin]);  // 找到前序遍历的第一个元素在中序遍历中的位置
        TreeNode root = new TreeNode(inorder[rootIndex]);  // 构造结点
        int lenOfLeft = rootIndex - inBegin;  // 保存中序左子树个数，用来确定前序数列的个数
        root.left = findNode(preorder, preBegin + 1, preBegin + lenOfLeft + 1,  
                            inorder, inBegin, rootIndex);
        root.right = findNode(preorder, preBegin + lenOfLeft + 1, preEnd,
                            inorder, rootIndex + 1, inEnd);

        return root;
    }
}

前序与后序遍历序列能构造二叉树吗？

不可以，因为没有中序的话是不能确定左右子树的

image-20220831082819708

tree1 的前序遍历是[1 2 3]， 后序遍历是[3 2 1]。

tree2 的前序遍历是[1 2 3]， 后序遍历是[3 2 1]。

那么tree1 和 tree2 的前序和后序完全相同，这是一棵树么，很明显是两棵树！

所以前序和后序不能唯一确定一棵二叉树

654. 最大二叉树

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

创建一个根节点，其值为 nums 中的最大值。
递归地在最大值 左边 的 子数组前缀上 构建左子树。
递归地在最大值 右边 的 子数组后缀上 构建右子树。
返回 nums 构建的 最大二叉树 。

image-20220831085051739

示例 1：

输入：nums = [3,2,1,6,0,5]
输出：[6,3,5,null,2,0,null,null,1]
解释：递归调用如下所示：

  • [3,2,1,6,0,5] 中的最大值是 6 ，左边部分是 [3,2,1] ，右边部分是 [0,5] 。
    • [3,2,1] 中的最大值是 3 ，左边部分是 [] ，右边部分是 [2,1] 。
      • 空数组，无子节点。
      • [2,1] 中的最大值是 2 ，左边部分是 [] ，右边部分是 [1] 。
        • 空数组，无子节点。
        • 只有一个元素，所以子节点是一个值为 1 的节点。
    • [0,5] 中的最大值是 5 ，左边部分是 [0] ，右边部分是 [] 。
      • 只有一个元素，所以子节点是一个值为 0 的节点。
      • 空数组，无子节点。

image-20220831085103058

思路

构造树一般采用的是前序遍历，因为先构造中间节点，然后递归构造左子树和右子树。

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

参数就是传入的是存放元素的数组，返回该数组构造的二叉树的头结点，返回类型是指向节点的指针。

TreeNode construtMaximumBinaryTree(ArrayList<Integer> nums)
  • 确定终止条件

题目中说了输入的数组大小一定是大于等于1的，所以我们不用考虑小于1的情况，那么当递归遍历的时候，如果传入的数组大小为1，说明遍历到了叶子节点了。

那么应该定义一个新的节点，并把这个数组的数值赋给新的节点，然后返回这个节点。 这表示一个数组大小是1的时候，构造了一个新的节点，并返回。

TreeNode node = new TreeNode(0);
if(nums.size() == 1){
	node.val = nums[0];
	return node;
}
  • 确定单层递归的逻辑

这里逻辑有三步工作分别是

  1. 找到数组中最大的值和对应的下标，最大的值构造根节点，下标用来下一步分割数组
int maxValue = 0;
int maxValueIndex = 0;
for(int i = 0; i<nums.sieze(); i++){
	if[nums[i] > maxValue]{
		maxValue = nums[i];
		maxValueIndex = i;
	}
}
TreeNode node = new TreeNode(0);
  1. 最大值所在的下标左区间 构造左子树
root.left = constructMaximumBinaryTree1(nums, leftIndex, maxIndex);
  1. 最大值所在下标右区间构造右子树
root.right = constructMaximumBinaryTree1(nums, maxIndex + 1, rightIndex);

代码如下：

/**
 * Definition for a binary tree node.
 * 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;
 *     }
 * }
 */
class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return constructMaximumBinaryTree1(nums, 0, nums.length);
    }

    public TreeNode constructMaximumBinaryTree1(int[] nums, int leftIndex, int rightIndex) {
        //边界条件的判断
        if (rightIndex - leftIndex < 1) {// 没有元素了
            return null;
        }
        //终止条件
        if (rightIndex - leftIndex == 1) {// 只有一个元素
            return new TreeNode(nums[leftIndex]);
        }
        //确定单层递归的逻辑
            //1.找到数组中的最大值作为根节点
            //2.根据maxIndex划分左子树
            //3.划分右子树
        int maxIndex = leftIndex;// 最大值所在位置
        int maxVal = nums[maxIndex];// 最大值
        for (int i = leftIndex + 1; i < rightIndex; i++) {
            if (nums[i] > maxVal){
                maxVal = nums[i];
                maxIndex = i;
            }
        }
        TreeNode root = new TreeNode(maxVal);
        // 根据maxIndex划分左右子树
        // 左闭右开：[left, maxValueIndex)
        root.left = constructMaximumBinaryTree1(nums, leftIndex, maxIndex);
        // 左闭右开：[maxValueIndex + 1, right)
        root.right = constructMaximumBinaryTree1(nums, maxIndex + 1, rightIndex);
        return root;
    }
}

构造二叉树有三个注意的点：

  • 分割时候，坚持区间不变量原则，左闭右开，或者左闭又闭。
  • 分割的时候，注意后序 或者 前序已经有一个节点作为中间节点了，不能继续使用了。
  • 如何使用切割后的后序数组来切合中序数组？利用中序数组大小一定是和后序数组的大小相同这一特点来进行切割。

相关文章：

  • 【学习教程】MCM箱模型建模方法及大气O3来源解析实践技术应用
  • IDEA配置
  • 这可能是目前最全的Redis高可用技术解决方案
  • FLASH：一种高效的Transformer设计
  • SpringBoot 和 Vue前后端分离在线工具项目实战，源码+超详细讲解
  • 【前端技术】Vue3 技术学习笔记
  • JS中4种常见的内存泄漏
  • 详解Shiro认证流程
  • 金山办公：订阅为王？
  • 【JavaEE】Spring AOP （面向切面）详解
  • java基于ssm的快递物流管理系统
  • SETTLE约束算法中的坐标变换问题
  • 基于python的家政管理系统毕业设计源码071111
  • SpringBoot基础篇 (3)——基础配置
  • springboot基于web的在线问答社区系统设计与实现毕业设计源码061628
  • angular组件开发
  • Asm.js的简单介绍
  • axios 和 cookie 的那些事
  • Hexo+码云+git快速搭建免费的静态Blog
  • Java教程_软件开发基础
  • js作用域和this的理解
  • k8s如何管理Pod
  • Mysql优化
  • scala基础语法(二)
  • UMLCHINA 首席专家潘加宇鼎力推荐
  • Vue 动态创建 component
  • webpack+react项目初体验——记录我的webpack环境配置
  • 基于Volley网络库实现加载多种网络图片（包括GIF动态图片、圆形图片、普通图片）...
  • 腾讯优测优分享 | 你是否体验过Android手机插入耳机后仍外放的尴尬？
  • 通过几道题目学习二叉搜索树
  • 推荐一款sublime text 3 支持JSX和es201x 代码格式化的插件
  • 为什么要用IPython/Jupyter?
  • 移动端解决方案学习记录
  • 阿里云移动端播放器高级功能介绍
  • ​你们这样子，耽误我的工作进度怎么办？
  • #每天一道面试题# 什么是MySQL的回表查询
  • （附源码）springboot“微印象”在线打印预约系统 毕业设计 061642
  • (附源码)springboot金融新闻信息服务系统 毕业设计651450
  • (欧拉)openEuler系统添加网卡文件配置流程、(欧拉)openEuler系统手动配置ipv6地址流程、(欧拉)openEuler系统网络管理说明
  • (转)Oracle存储过程编写经验和优化措施
  • .dwp和.webpart的区别
  • .java 指数平滑_转载：二次指数平滑法求预测值的Java代码
  • .net 7 上传文件踩坑
  • .net core IResultFilter 的 OnResultExecuted和OnResultExecuting的区别
  • .net core 调用c dll_用C++生成一个简单的DLL文件VS2008
  • .NET delegate 委托 、 Event 事件
  • .NET基础篇——反射的奥妙
  • /etc/fstab 只读无法修改的解决办法
  • @RequestMapping用法详解
  • [＜事务专题＞]
  • [Android] Android ActivityManager
  • [Assignment] C++1
  • [BUUCTF NewStarCTF 2023 公开赛道] week3 crypto/pwn
  • [CSS] 点击事件触发的动画
  • [C语言]——C语言常见概念（1）