网站开发摘要,wordpress页面跳舞,东莞阿里网站设计,wordpress电台文章目录 1.【513】找树左下角的值1.1题目描述1.2 解题思路1.2.1 迭代法思路1.2.2 递归法思路 1.3 java代码实现1.3.1 迭代法java代码实现1.3.2 递归法java代码实现 2. 【112】路径总和2.1题目描述2.2 解题思路2.3 java代码实现 3.【106】从中序与后序遍历序列构造二叉树3.1题目… 文章目录 1.【513】找树左下角的值1.1题目描述1.2 解题思路1.2.1 迭代法思路1.2.2 递归法思路 1.3 java代码实现1.3.1 迭代法java代码实现1.3.2 递归法java代码实现 2. 【112】路径总和2.1题目描述2.2 解题思路2.3 java代码实现 3.【106】从中序与后序遍历序列构造二叉树3.1题目描述3.2 解题思路3.3 java代码实现 【513】找树左下角的值 【112】路径总和 【106】从中序与后序遍历序列构造二叉树 1.【513】找树左下角的值
1.1题目描述
给定一个二叉树的 根节点 root请找出该二叉树的 最底层 最左边 节点的值。
假设二叉树中至少有一个节点。 提示:
二叉树的节点个数的范围是 [1,104]-231 Node.val 231 - 1
1.2 解题思路
1.2.1 迭代法思路
本题要找出树的最后一行的最左边的值使用层序遍历是非常简单的只需要记录最后一行第一个节点的数值就可以了。
1.2.2 递归法思路
题目在树的最后一行找到最左边的值。
首先要是最后一行然后是最左边的值。
如果使用递归法如何判断是最后一行呢其实就是深度最大的叶子节点一定是最后一行。所以要找深度最大的叶子节点。
那么如何找最左边的呢可以使用前序遍历当然中序后序都可以因为本题没有 根节点的处理逻辑只要左优先就行保证优先左边搜索然后记录深度最大的叶子节点此时就是树的最后一行最左边的值。 递归三部曲 确定递归函数的参数和返回值
参数必须有要遍历的树的根节点还有就是一个int型的变量用来记录最长深度。 这里就不需要返回值了所以递归函数的返回类型为void。
本题还需要类里的两个全局变量maxDepth用来记录最大深度result记录最大深度最左节点的数值。 int result;// 全局变量 记录最大深度int maxDepth-1;// 全局变量 最大深度最左节点的数值public void traversal(TreeNode root,int depth)确定终止条件
当遇到叶子节点的时候就需要统计一下最大的深度了所以需要遇到叶子节点来更新最大深度。 if (root.leftnull root.rightnull){if (depthmaxDepth){maxDepthdepth;// 更新最大深度resultroot.val;// 最大深度最左面的数值}return;}确定单层递归的逻辑
在找最大深度的时候递归的过程中依然要使用回溯 if (root.left!null){//左depth;traversal(root.left,depth);//回溯depth--;}if (root.right!null){//右depth;traversal(root.right,depth);//回溯depth--;}return;1.3 java代码实现
1.3.1 迭代法java代码实现
class Solution {public int findBottomLeftValue(TreeNode root) {//迭代法 层次遍历QueueTreeNode quenew LinkedList();que.offer(root);int res0;while (!que.isEmpty()){int lenque.size();for (int i 0; i len; i) {TreeNode tempNodeque.poll();// 记录最后一行第一个元素if (i0){restempNode.val;}if (tempNode.left!null){que.offer(tempNode.left);}if (tempNode.right!null){que.offer(tempNode.right);}}}return res;}
}1.3.2 递归法java代码实现
class Solution {int result;// 全局变量 记录最大深度int maxDepth-1;// 全局变量 最大深度最左节点的数值public int findBottomLeftValue(TreeNode root) {//递归traversal(root,0);return result;}public void traversal(TreeNode root,int depth){if (root.leftnull root.rightnull){if (depthmaxDepth){maxDepthdepth;// 更新最大深度resultroot.val;// 最大深度最左面的数值}return;}if (root.left!null){//左depth;traversal(root.left,depth);//回溯depth--;}if (root.right!null){//右depth;traversal(root.right,depth);//回溯depth--;}return;}
}递归函数简写 public void traversal(TreeNode root,int depth){if (root.leftnull root.rightnull){if (depthmaxDepth){maxDepthdepth;// 更新最大深度resultroot.val;// 最大深度最左面的数值}return;}if (root.left!null){//左traversal(root.left,depth1);// 隐藏着回溯}if (root.right!null){//右traversal(root.right,depth1);// 隐藏着回溯}return;}2. 【112】路径总和
2.1题目描述
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径这条路径上所有节点值相加等于目标和 targetSum 。如果存在返回 true 否则返回 false 。
叶子节点 是指没有子节点的节点。 提示
树中节点的数目在范围 [0, 5000] 内-1000 Node.val 1000-1000 targetSum 1000
2.2 解题思路
本题可以采用深度遍历的方式来遍历本题前中后序都可以无所谓因为根节点也没有处理逻辑。递归法 2.3 java代码实现
class Solution {public boolean hasPathSum(TreeNode root, int targetSum) {if (rootnull){return false;}targetSum - root.val;//叶子结点if (root.leftnull root.rightnull){return targetSum0;}if (root.left!null){boolean lefthasPathSum(root.left,targetSum);//已经找到if (left){return true;}}if (root.right!null){boolean righthasPathSum(root.right,targetSum);//已经找到if (right){return true;}}return false;}
}3.【106】从中序与后序遍历序列构造二叉树
3.1题目描述
给定两个整数数组 inorder 和 postorder 其中 inorder 是二叉树的中序遍历 postorder 是同一棵树的后序遍历请你构造并返回这颗 二叉树 。 提示:
1 inorder.length 3000postorder.length inorder.length-3000 inorder[i], postorder[i] 3000inorder 和 postorder 都由 不同 的值组成postorder 中每一个值都在 inorder 中inorder 保证是树的中序遍历postorder 保证是树的后序遍历
3.2 解题思路 中序遍历与后序遍历构造二叉树的理论知识 以 后续数组的最后一个元素为切割点先切中序数组根据中序数组反过来再切后续数组。一层一层的切下去每次后续数组的最后一个元素就是节点元素。
流程如下 代码该怎样写呢提到一层一层切割就应该想到了递归 如果数组大小为0的话说明是空节点了 如果不为空那么取后序数组的最后一个元素作为节点元素 找到后序数组最后一个元素在中序数组中的位置作为切割点 切割中序数组切成中序左数组和中序右数组顺序一定不能弄反了一定要先切中序数组 切割后序数组切成后序左数组和后序右数组 递归处理左区间和右区间
3.3 java代码实现
class Solution {public TreeNode buildTree(int[] inorder, int[] postorder) {if (postorder.length0 || inorder.length0){return null;}return buildHelper(inorder,0,inorder.length,postorder,0, postorder.length);}public TreeNode buildHelper(int[] inorder,int inorderBegin,int inorderEnd,int[] postorder,int postBegin,int postEnd){if (postBeginpostEnd){return null;}//根节点int rootValpostorder[postEnd-1];TreeNode rootnew TreeNode(rootVal);//切割点int middleIndex;for (middleIndexinorderBegin;middleIndexinorderEnd;middleIndex){if (inorder[middleIndex]rootVal){break;}}//切割中序数组//左中序数组左闭右开[leftInorderBegin,leftInoderEnd)int leftInorderBegininorderBegin;int leftInoderEndmiddleIndex;//右中序数组左闭右开[rightInorderBegin,leftInoderEnd)int rightInorderBeginmiddleIndex1;int rightInoderEndinorderEnd;//切割后序数组//左后序数组左闭右开[leftPostorderBegin,leftPostoderEnd)int leftPostorderBeginpostBegin;//终止位置是 需要加上 中序区间的大小sizeint leftPostoderEndpostBegin(middleIndex-inorderBegin);//右后序数组左闭右开[rightPostorderBegin,leftPostoderEnd)int rightPostorderBeginleftPostoderEnd;int rightPostoderEndpostEnd-1;//排除最后一个元素已经作为节点了root.leftbuildHelper(inorder,leftInorderBegin,leftInoderEnd,postorder,leftPostorderBegin,leftPostoderEnd);root.rightbuildHelper(inorder,rightInorderBegin,rightInoderEnd,postorder,leftPostorderBegin,rightPostoderEnd);return root;}
}class Solution {MapInteger,Integer map;//方便根据数值查找位置public TreeNode buildTree(int[] inorder, int[] postorder) {mapnew HashMap();// 用map保存中序序列的数值对应位置for (int i0;iinorder.length;i){map.put(inorder[i],i );}return findNode(inorder,0,inorder.length,postorder,0,postorder.length);}public TreeNode findNode(int[] inorder,int inorderBegin,int inorderEnd,int[] postorder,int postBegin,int postEnd){//参数里的范围都是左闭右开if (inorderBegininorderEnd || postBeginpostEnd){return null;}// 找到后序遍历的最后一个元素在中序遍历中的位置int rootIndexmap.get(postorder[postEnd-1]);TreeNode rootnew TreeNode(inorder[rootIndex]);//构造节点//保存中序左子树个数用来确定后序数列的个数int lenOfleftrootIndex-inorderBegin;root.leftfindNode(inorder,inorderBegin,rootIndex,postorder,postBegin,postBeginlenOfleft);root.rightfindNode(inorder,rootIndex1,inorderEnd,postorder,postBeginlenOfleft,postEnd-1);return root;}}
