商城建设网站公司,部标平台软件网站开发,竞价关键词优化软件,电脑字体wordpress找树左下角的值
题目
参考文章 思路#xff1a;这里寻找最左下角的值#xff0c;其实用前中后序都是可以的#xff0c;只要保证第一遍历的是左边开始就可以。设置Deep记录遍历的最大深度#xff0c;deep记录当前深度。当遇到叶子节点时而且当前深度比最大深度还大则更换最…找树左下角的值
题目
参考文章 思路这里寻找最左下角的值其实用前中后序都是可以的只要保证第一遍历的是左边开始就可以。设置Deep记录遍历的最大深度deep记录当前深度。当遇到叶子节点时而且当前深度比最大深度还大则更换最大深度为deep并存储当前节点的值这个时候说明遇到的就是当前深度下最左边的叶子节点但不一定是最最大深度的最左边的叶子节点还要继续往后遍历。最后value存储的结果就是最大深度下最左下角的值了 代码
class Solution {private int Deep -1;private int value 0;public int findBottomLeftValue(TreeNode root) {value root.val;findLeftValue(root,0);return value;}private 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);}
}
路径总和
题目1
题目2
参考文章 思路1其实这里的用前中后序都是可以的重要的是回溯的过程。每次遍历节点就把target值减去当前节点值然后判断是否为叶子节点如果是叶子节点就直接返回true因为题目意思就是遇到一条路径等于target值就直接返回即可。当不是叶子节点且节点不为空就继续遍历节点值直到遇到一条路径等于target就一直返回true到根节点否则就是返回false 代码1
class Solution {public boolean hasPathSum(TreeNode root, int targetSum) {if (root null) {return false;}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;}
}
思路2
这题和题目1其实思路一样只是不是直接返回true而是把这条路径的值全部存起来最后把所有等于target值的路径输出
代码2
class Solution {public ListListInteger pathSum(TreeNode root, int targetSum) {ListListInteger res new ArrayList();if (root null) return res; ListInteger path new LinkedList();preorderdfs(root, targetSum, res, path);return res;}public void preorderdfs(TreeNode root, int targetsum, ListListInteger res, ListInteger path) {path.add(root.val);// 遇到了叶子节点if (root.left null root.right null) {// 找到了和为 targetsum 的路径if (targetsum - root.val 0) {res.add(new ArrayList(path));}return; // 如果和不为 targetsum返回}if (root.left ! null) {preorderdfs(root.left, targetsum - root.val, res, path);path.remove(path.size() - 1); // 回溯}if (root.right ! null) {preorderdfs(root.right, targetsum - root.val, res, path);path.remove(path.size() - 1); // 回溯}}
} 从中序与后序遍历序列构造二叉树
题目
参考文章 思路其实这道题就是理解二叉树的一个过程构建二叉树首先得知道前序中序或中序后序知道前序后序是不能构造二叉树的。以后序中序为例这里重要的是找到根节点以及找到根节点后如何分割这个后序中序数组。后序数组中最后一个元素就是根节点然后通过这个根节点的值找到在对应中序的下标index找到下标之后就是分割后序中序数组通过index找到左中序右中序以及左后序和右后序重点注意右中序因为涉及数组溢出和超出数组范围的情况主要是因为在中序数组中间会出现要构建子树的情况得到分割后的数组就继续调用构建树的方法即可 代码
class Solution {public TreeNode buildTree(int[] inorder, int[] postorder) {if(postorder.length 0 || inorder.length 0)return null;return buildHelper(inorder, 0, inorder.length, postorder, 0, postorder.length);}private TreeNode buildHelper(int[] inorder, int inorderStart, int inorderEnd, int[] postorder, int postorderStart, int postorderEnd){if(postorderStart postorderEnd)return null;int rootVal postorder[postorderEnd - 1];TreeNode root new TreeNode(rootVal);int middleIndex;for (middleIndex inorderStart; middleIndex inorderEnd; middleIndex){if(inorder[middleIndex] rootVal)break;}int leftInorderStart inorderStart; int leftInorderEnd middleIndex;int rightInorderStart middleIndex 1;int rightInorderEnd inorderEnd;int leftPostorderStart postorderStart;int leftPostorderEnd postorderStart (middleIndex - inorderStart);//这个是为了防止数组溢出因为有可能中序数组中间部分是要构建树的所以postorderStart和inorderStart可能不为零的情况所以要减去int rightPostorderStart leftPostorderEnd;int rightPostorderEnd postorderEnd - 1;root.left buildHelper(inorder, leftInorderStart, leftInorderEnd, postorder, leftPostorderStart, leftPostorderEnd);root.right buildHelper(inorder, rightInorderStart, rightInorderEnd, postorder, rightPostorderStart, rightPostorderEnd);return root;}
}
