vue做网站的好处,关键词排名监控批量查询,怎样制作一个自己的网站,创意网络营销案例一、寻找特定节点
1. 404【左叶子之和】
题目#xff1a; 给定二叉树的根节点 root #xff0c;返回所有左叶子之和。代码#xff1a;
class Solution {public int sumOfLeftLeaves(TreeNode root) {//左叶子不止是最左边的叶子#xff0c;而是二叉树中每个节点的左叶子…一、寻找特定节点
1. 404【左叶子之和】
题目 给定二叉树的根节点 root 返回所有左叶子之和。代码
class Solution {public int sumOfLeftLeaves(TreeNode root) {//左叶子不止是最左边的叶子而是二叉树中每个节点的左叶子//每棵树的左叶子之和左子树左叶子之和右子树左叶子之和//其中左子树可能是一个叶子节点它的左叶子之和就是它本身if(root null) return 0;int leftSum 0;if(root.left!null root.left.leftnull root.left.rightnull){leftSum root.left.val;}else{leftSum sumOfLeftLeaves(root.left);}int right sumOfLeftLeaves(root.right);return leftSumright;}
}2. 513【找树左下角的值】
题目 给定一个二叉树的 根节点 root请找出该二叉树的最底层最左边节点的值。假设二叉树中至少有一个节点。代码
class Solution {public int findBottomLeftValue(TreeNode root) {//最底层最左边也就是层序遍历最后一层的第一个节点DequeTreeNode queue new ArrayDeque();queue.offer(root);TreeNode ansNode root;while (!queue.isEmpty()){int len queue.size(); //必须提前声明因为每次循环queue的长度都会变化for (int i 0; i len; i) {TreeNode tempNode queue.poll();if(i 0){ansNode tempNode;}if(tempNode.left ! null){queue.offer(tempNode.left);}if(tempNode.right ! null){queue.offer(tempNode.right);}}}return ansNode.val;}
}二、构造二叉树
1. 106【从中序与后序遍历序列构造二叉树】
题目 给定两个整数数组 inorder 和 postorder 其中 inorder 是二叉树的中序遍历 postorder 是同一棵树的后序遍历请你构造并返回这颗 二叉树 。代码
class Solution {public TreeNode buildSubTree(int[] inorder,int inStart,int inEnd,int[] postorder,int postStart,int postEnd){//如果后序遍历数组为空则表示该部分节点构建完成if(postEnd postStart){return null;}TreeNode root new TreeNode(postorder[postEnd-1]);int middle;for (middle inStart; middle inEnd ; middle) {if(inorder[middle] postorder[postEnd-1]){break;}}//注意后续遍历数组的分割点TreeNode leftNode buildSubTree(inorder,inStart,middle,postorder,postStart,postStartmiddle-inStart);TreeNode rightNode buildSubTree(inorder,middle1,inEnd,postorder,postStartmiddle-inStart,postEnd-1);root.left leftNode;root.right rightNode;return root;}public TreeNode buildTree(int[] inorder, int[] postorder) {//已知中序遍历和前序遍历可以确定唯一二叉树//已知中序遍历和后序遍历可以确定唯一二叉树//因为后序遍历为左右根所以后序遍历数组中最后一个元素为二叉树的根//在中序遍历数组中根的左边为根的左子树根的右边为根的右子树//因为中序遍历为左根右所以在中序遍历中根的左边有n个节点//在后序遍历中最左边n个节点构成根的左子树if(inorder.length0 || postorder.length0) return null;//首先找到根根据根划分后序遍历数组//然后根据后序遍历数组划分中序遍历数组TreeNode root buildSubTree(inorder,0,inorder.length,postorder,0,postorder.length);return root;}
}2. 105【从前序与中序遍历序列构造二叉树】
题目 给定两个整数数组 preorder 和 inorder 其中 preorder 是二叉树的先序遍历 inorder 是同一棵树的中序遍历请构造二叉树并返回其根节点。代码
class Solution {public TreeNode buildSubTree(int[] preorder,int preStart,int preEnd,int[] inorder,int inStart,int inEnd){if(preEnd preStart){return null;}TreeNode root new TreeNode(preorder[preStart]);int middle;for(middleinStart;middleinEnd;middle){if(preorder[preStart] inorder[middle]){break;}}TreeNode leftNode buildSubTree(preorder,preStart1,preStart1middle-inStart,inorder,inStart,middle);TreeNode rightNode buildSubTree(preorder,preStart1middle-inStart,preEnd,inorder,middle1,inEnd);root.left leftNode;root.right rightNode;return root;}public TreeNode buildTree(int[] preorder, int[] inorder) {//与上一题相似只是这里在前序遍历数组由前向后遍历if(preorder.length0 || inorder.length0){return null;}return buildSubTree(preorder,0,preorder.length,inorder,0,inorder.length);}
}3. 654【最大二叉树】
题目 给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建: 1创建一个根节点其值为 nums 中的最大值。 2递归地在最大值 左边 的 子数组前缀上 构建左子树。 3递归地在最大值 右边 的 子数组后缀上 构建右子树。 4返回 nums 构建的 最大二叉树 。代码
class Solution {public TreeNode constructMaximumBinaryTree(int[] nums) {//首先找到最大值根据最大值划分数组//最大值左边组成左子树最大值右边组成右子树最大值构建根//左子树右子树递归构建//递归时需要传入所有要进行构建树的值因此需要return constructTree(nums,0,nums.length);}public TreeNode constructTree(int[] nums,int start, int end){if(end start){return null;}int max nums[start];int index start;for (int i start; i end; i) {if(nums[i]max){index i;max nums[i];}}TreeNode root new TreeNode(nums[index]);TreeNode leftNode constructTree(nums,start,index);TreeNode rightNode constructTree(nums,index1,end);root.left leftNode;root.right rightNode;return root;}
}4. 617【合并二叉树】
题目 给你一个链表的头节点 head 和一个整数 val 请你删除链表中所有满足 Node.val val 的节点并返回 新的头节点 。代码
class Solution {public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {//在一棵树的基础上操作直接加上另一棵树该位置的值如果为null值为0//采用前序遍历终止条件为一棵树遍历完成if(root1 null) return root2;if(root2 null) return root1;root1.val root1.valroot2.val;root1.left mergeTrees(root1.left,root2.left);root1.right mergeTrees(root1.right,root2.right);return root1;}
}
