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

news/2024/5/18 18:24:13/文章来源:https://blog.csdn.net/qq_45714272/article/details/126617270

二叉树篇（二）

  • 前言
  • 完全二叉树的节点个数
    • 普通二叉树逻辑
      • 递归
    • 完全二叉树逻辑
  • 平衡二叉树
    • 题外话
    • 递归
  • 二叉树的所有路径
    • 思路
    • 递归
  • 相同的树
    • 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^leftDepthreturn (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;}// 返回以该节点为根节点的二叉树的高度，如果不是平衡二叉树了则返回-1public 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表中的keyint 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;}
}

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

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

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.luyixian.cn/news_show_3400.aspx

如若内容造成侵权/违法违规/事实不符，请联系dt猫网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

FLASH：一种高效的Transformer设计

FLASH：一种高效的Transformer设计

背景 近年来&#xff0c;Transformer凭借其优秀的设计&#xff0c;在文本、图像、语音等方向大杀四方。但是由于其attention的二次复杂度限制了其在长序列上的应用。本文提出了一种快(速度快)、省(省显存)的模型FLASH(Fast Linear Attention with a Single Head)&#xff0c;在…
阅读更多...
SpringBoot 和 Vue前后端分离在线工具项目实战，源码+超详细讲解

SpringBoot 和 Vue前后端分离在线工具项目实战，源码+超详细讲解

一、前言 主要通过SpringBoot和Vue来实现一个前后端分离的在线工具平台&#xff0c;包含PDF转换、图片处理、文本处理、图表展示、二维码工具等功能。 为了更直观展示项目效果&#xff0c;也给大家提供了在线体验地址&#xff1a;http://49.234.28.149, 源码资源见文末。 通过…
阅读更多...
org.apache.ibatis.binding.BindingException: Invalid bound statement (not found):

org.apache.ibatis.binding.BindingException: Invalid bound statement (not found):

org.apache.ibatis.binding.BindingException: Invalid bound statement (not found): 无效的绑定语句（未找到），就是写的sql 方法找不到sql。解决： 1 namespace 指向是否正确 路径与引用的方法的路径保持一致a.namespace 没有指向Dao b. id ,方法名没有对应上2 引用的方法…
阅读更多...
记录Kettle连不上mysql8

记录Kettle连不上mysql8

如图所示&#xff0c;mysql升级到8了。 在很早之前&#xff0c;我一直用的是Mysql 5的驱动包去连接数据库&#xff0c;今天发现突然连接不上了&#xff0c;想了一下&#xff0c;应该是我以前升级mysql后的原因&#xff0c;换了mysql8的驱动后依旧没个卵用。 报错如下&#xff…
阅读更多...
远程Debug远端服务器JVM配置

远程Debug远端服务器JVM配置

远程调试非本机的Java进程 远端Java进程启动的JVM参数 注意&#xff1a;以下配置尽量不要在线上生产环境开启&#xff0c;或者 JDK4: -Xdebug -Xrunjdwp:transportdt_socket,servery,suspendn,address{port} JDK5-JDK8: -agentlib:jdwptransportdt_socket,servery,suspen…
阅读更多...
Python——LeetCode刷题——【383. 赎金信】

Python——LeetCode刷题——【383. 赎金信】

题目描述&#xff1a; 解题思路&#xff1a; 用字典记录字符串magazine中每个字符出现的次数。然后看看字典中magazine的各个字符的出现次数是否“够”字符串ransomNote中各个字符出现的次数。如果够&#xff0c;return True。如果存在有点字符不够&#xff0c;return False。…
阅读更多...
学习：Python进阶 冒泡排序

学习：Python进阶 冒泡排序

#原理 列表每两个相邻的数，如果前面的数比后面的数大，则交换这两个数 一趟排序完成后，则无序曲减少一个数，有序区增加一个数 每循环一趟，从无序区冒出来一个最大的数，放入有序区，最终得到一个升序的列表
阅读更多...
认真研究ConcurrentHashMap中的元素统计策略

认真研究ConcurrentHashMap中的元素统计策略

这里我们想研究的是jdk1.8中ConcurrentHashMap的addCount(long x, int check)方法。如下所示在put方法的最后会触发addCount(long x, int check)方法进行元素个数的统计。 我们再回顾一下另一个参数binCount &#xff1a; 在操作链表的分支if (fh > 0)中 用于统计put前链表…
阅读更多...
TinyRenderer学习笔记--Lesson 3、4

TinyRenderer学习笔记--Lesson 3、4

Lesson 3 zbuffer 无论怎样&#xff0c;生活中的显示器基本上都是平面&#xff0c;是一个2D的场景&#xff0c;而我们的模型却是3D的&#xff0c;是有深度的&#xff0c;实际上我们看见的都只是离我们的眼睛最近的那一个平面&#xff0c;一个不透明的3D物体的内部和背面是我们…
阅读更多...
河北稳控科技使用标准信号检测 VM振弦采集模块测量精度

河北稳控科技使用标准信号检测 VM振弦采集模块测量精度

河北稳控科技使用标准信号检测 VM振弦采集模块测量精度（一） （1）电源1.1VDD 引脚电源必须使用 LDO 稳压或者低纹波线性电源， LDO 推荐使用 AM1117_3.3V 芯片，测试时发现 SPX 生产的 LDO会造成非常严重的干扰（其它品牌应该也会有类似的问题）。1.2VSEN 引脚电源单通道模块…
阅读更多...
阿里、滴滴、华为等一线互联网分布式消息中间件：RocketMQ核心笔记

阿里、滴滴、华为等一线互联网分布式消息中间件：RocketMQ核心笔记

本篇介绍了RocketMQ的基本使用方法及其各个组件的基本原理&#xff0c;讲解原理时&#xff0c;都是采用先整体架构后详细分解的方式。详细分解时不会深入源码逐段讲&#xff0c;而是从代码结构出发梳理整个运行过程。 这份RocketMQ分布式消息中间件—核心原理与最佳实践的完整…
阅读更多...
Android Studio应用基础，手把手教你从入门到精通（小白学习）总结2 之 常用界面布局和ListView

Android Studio应用基础，手把手教你从入门到精通（小白学习）总结2 之 常用界面布局和ListView

总结1链接&#xff1a; (156条消息) Android Studio应用基础&#xff0c;手把手教你从入门到精通&#xff08;小白学习&#xff09;总结1_好喜欢吃红柚子的博客-CSDN博客 学习视频链接&#xff1a; &#xff08;学完必会&#xff09;Android studio基础&#xff0c;从入门到…
阅读更多...
尚好房 07_前端房源展示

尚好房 07_前端房源展示

尚好房&#xff1a;前端房源展示 一、分页显示房源列表 1、效果 2、项目搭建 2.1 创建项目 在web项目中创建子工程web-front 2.2 pom.xml <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0&…
阅读更多...
stm32学习(二)|ADC电压采集DMA

stm32学习(二)|ADC电压采集DMA

利用ADC通道采集外部传感器数值，ADC通道选择依据实际查询芯片手册可得，相关配置利用Cubemx完成。 ADC参数配置首先选择需要使用的ADC通道，并设置对应的引脚ADC_IN0X.ADC参数设置（Paremeter setting）Mode ： Independent mode，只使用一个ADC通道 Clock Prescaler，Resolut…
阅读更多...
OpenGL 反色

OpenGL 反色

目录 一.OpenGL 反色 1.IOS Object-C 版本2.Windows OpenGL ES 版本3.Windows OpenGL 版本 二.OpenGL 反色 GLSL Shader三.猜你喜欢 零基础 OpenGL ES 学习路线推荐 : OpenGL ES 学习目录 >> OpenGL ES 基础 零基础 OpenGL ES 学习路线推荐 : OpenGL ES 学习目录 >&…
阅读更多...
Windows OpenGL ES 图像反色

Windows OpenGL ES 图像反色

目录 一.OpenGL ES 图像反色 1.原始图片2.效果演示 二.OpenGL ES 图像反色源码下载三.猜你喜欢 零基础 OpenGL ES 学习路线推荐 : OpenGL ES 学习目录 >> OpenGL ES 基础 零基础 OpenGL ES 学习路线推荐 : OpenGL ES 学习目录 >> OpenGL ES 特效 零基础 OpenGL E…
阅读更多...
责任链模式

责任链模式

1、责任链模式是什么 行为模式&#xff0c;一个对象产生的消息会被另外的对象处理。对象发出消息后&#xff0c;不管被哪种、多少个其他对象收到和处理消息。【客户端和handler解耦】 2、为什么使用 如果不使用责任链&#xff0c;则client要知道有多少个handler、什么情况调…
阅读更多...
2.IP子网划分

2.IP子网划分

IP子网划分地址分类网络位与主机位一个网段可以容纳多少IPIP地址&#xff1a;互联网中计算机的‘身份证号’&#xff0c;唯一标识一台网络设备的身份ID NAT技术&#xff1a;网络地址转换&#xff0c;节约公网IP 例: IP地址 192.168.1.1 192.168.1 …
阅读更多...
电商数仓项目中各层的表

电商数仓项目中各层的表

ODS operation Data store 操作数据存储 DWD Data Warehouse detail 细节数据层, DIM Dimension---------------范围&#xff0c;维度 DWS Data Warehouse Summary 数据库汇总 ADS Application Data Service 应用数据服务层 【电商数仓每一层的表】 【ODS层】 operation Data s…
阅读更多...
Spring之AOP思想

Spring之AOP思想

目录 什么是AOP ​​​为什么用AOP Spring AOP 应该怎么学习呢 AOP下的一些核心概念&#xff08;SpringAOP并没有实现所有的概念&#xff09; 基于概念的使用Spring的AOP 一个使用的实例 关于切点的匹配 通知的种类 使用注解的方式来实现功能​编辑 AOP框架背后的核心 …
阅读更多...
推荐文章
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站 广利置业