现在都不用dw做网站了吗,做网站怎么选取关键词,东莞线上推广平台,网站制作需求分析目录
104.二叉树的最大深度
100.相同的树 226.翻转二叉树 101.对称二叉树 105.从前序与中序遍历序列构造二叉树 106.从中序与后序遍历序列构造二叉树 117.填充每个节点的下一个右侧节点指针Ⅱ 104.二叉树的最大深度 题意#xff1a; 给定一个二叉树 root #xff0c;返回其…目录
104.二叉树的最大深度
100.相同的树 226.翻转二叉树 101.对称二叉树 105.从前序与中序遍历序列构造二叉树 106.从中序与后序遍历序列构造二叉树 117.填充每个节点的下一个右侧节点指针Ⅱ 104.二叉树的最大深度 题意 给定一个二叉树 root 返回其最大深度。 二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。 【输入样例】 root[3,9,20,null,null,15,7] 【输出样例】 3 解题思路递归 class Solution {public int maxDepth(TreeNode root) {if(root null){return 0;}//1是当树的根节点不为空时加上根return 1 Math.max(maxDepth(root.right),maxDepth(root.left));}
} 时间 击败了100.00% 内存 击败了36.81% 100.相同的树 题意 给你两棵二叉树的根节点 p 和 q 编写一个函数来检验这两棵树是否相同。 如果两个树在结构上相同并且节点具有相同的值则认为它们是相同的。 【输入样例】 p[1,2,3], q[1,2,3] 【输出样例】 true 解题思路递归 1.先判断当前根节点的值是否一样 2.再判断是否都拥有左子树和右子树 3.递归判断左子树右子树 class Solution {public boolean isSameTree(TreeNode p, TreeNode q) {if(p null q null){return true;}//如果说两者都会null会在上面的分支语句返回true//这里判断的是只有一方为null的情况下if(p null || q null){return false;}//根都不为null判断值是否相同if(p.val ! q.val){return false;}return isSameTree(p.left,q.left)isSameTree(p.right,q.right);}
} 时间 击败了100.00% 内存 击败了41.80% 226.翻转二叉树 题意 给你一棵二叉树的根节点 root 翻转这棵二叉树并返回其根节点。 【输入样例】 root [4,2,7,1,3,6,9] 【输出样例】 [4,7,2,9,6,3,1] 解题思路递归 1. 不断将当前节点的左右子树交换递归实现 class Solution {public TreeNode invertTree(TreeNode root) {if(root null){return root;}//左右子树交换TreeNode temp root.right;root.right root.left;root.left temp;//交换左子树invertTree(root.left);//交换右子树invertTree(root.right);return root;}
} 时间 击败了100.00% 内存 击败了88.10% 101.对称二叉树 题意 给你一个二叉树的根节点 root 检查它是否轴对称。 【输入样例】 root [1,2,2,3,4,4,3] 【输出样例】 true 解题思路递归 1. 递归函数判断节点的左子树和右子树是否对称把左子树和右子树拆开题目就转变成了判断相同的树了。 class Solution {public boolean isSymmetric(TreeNode root) {if(root null){return true;}return cmp(root.left, root.right);}public boolean cmp(TreeNode root1, TreeNode root2){if(root1 null root2 null){return true;}if(root1 null || root2 null || root1.val ! root2.val){return false;}return cmp(root1.left,root2.right) cmp(root1.right,root2.left);}
} 时间 击败了100.00% 内存 击败了82.85% 105.从前序与中序遍历序列构造二叉树 题意 给定两个整数数组 preorder 和 inorder 其中 preorder 是二叉树的先序遍历 inorder 是同一棵树的中序遍历请构造二叉树并返回其根节点。 【输入样例】 preorder [3,9,20,15,7], inorder [9,3,15,20,7] 【输出样例】 [3,9,20,null,null,15,7] 解题思路 1. 先序遍历的过程是根 左 右中序遍历的过程是左 根 右。 2. 根据规律首先需要找到的是根节点inorder数组中根左边的是左子树根右边的是右子树 3. 之后分别构造左子树和右子树 /*** 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 MapInteger,Integer indexMap;public TreeNode buildTree(int[] preorder, int[] inorder) {int n preorder.length;//一共n个节点//构造哈希映射快速定位根节点indexMap new HashMapInteger,Integer();for(int i0;in;i){indexMap.put(inorder[i],i);}return myBuildTree(preorder,inorder,0,n-1,0,n-1);}public TreeNode myBuildTree(int[] preorder, int[] inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right) {if (preorder_left preorder_right) {return null;}//前序遍历找到根节点int preorder_root preorder_left;//中序遍历定位根节点int inorder_root indexMap.get( preorder[preorder_root]);//建立根节点TreeNode root new TreeNode(preorder[preorder_root]);//确定左子树节点数目int size_left_subtree inorder_root - inorder_left;//递归构造左子树连接到根节点root.left myBuildTree(preorder,inorder,preorder_left1,preorder_leftsize_left_subtree,inorder_left, inorder_root-1);//递归构造右子树root.right myBuildTree(preorder,inorder,preorder_leftsize_left_subtree1, preorder_right,inorder_root1, inorder_right);return root;}
} 时间 击败了99.18% 内存 击败了23.53% 106.从中序与后序遍历序列构造二叉树 题意 给定两个整数数组 inorder 和 postorder 其中 inorder 是二叉树的中序遍历 postorder 是同一棵树的后序遍历请你构造并返回这颗 二叉树 。 【输入样例】 inorder [9,3,15,20,7]postorder [9,15,7,20,3] 【输出样例】 [3,9,20,null,null,15,7] 解题思路 1. 中序遍历的过程是左 根 右; 后序遍历的过程是左 右 根 。 2. 根据规律首先需要找到的是根节点inorder数组中根左边的是左子树根右边的是右子树 3. 之后分别构造左子树和右子树 class Solution {private MapInteger,Integer indexMap;public TreeNode buildTree(int[] inorder, int[] postorder) {int n postorder.length;//一共n个节点//构造哈希映射快速定位根节点indexMap new HashMapInteger,Integer();for(int i0;in;i){indexMap.put(inorder[i],i);}return myBuildTree(inorder,postorder,0,n-1,0,n-1);}public TreeNode myBuildTree(int[] inorder,int[] postorder, int inorder_left, int inorder_right,int postorder_left, int postorder_right) {if (postorder_left postorder_right || inorder_left inorder_right) {return null;}//后序遍历找到根节点int postorder_root postorder[postorder_right];//中序遍历定位根节点int inorder_root indexMap.get(postorder_root);//建立根节点TreeNode root new TreeNode(postorder_root);//确定左子树节点数目int size_left_subtree inorder_root - inorder_left;//递归构造左子树连接到根节点root.left myBuildTree(inorder, postorder, inorder_left, inorder_root-1,postorder_left,postorder_leftsize_left_subtree-1);//递归构造右子树root.right myBuildTree(inorder,postorder, inorder_root1, inorder_right,postorder_leftsize_left_subtree,postorder_right-1);return root;}
} 时间 击败了99.21% 内存 击败了61.89% 117.填充每个节点的下一个右侧节点指针Ⅱ 题意 给定一个二叉树 struct Node {int val;Node *left;Node *right;Node *next;
} 填充它的每个 next 指针让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点则将 next 指针设置为 NULL 。 初始状态下所有 next 指针都被设置为 NULL 。 【输入样例】 root[1,2,3,4,5,null,7] 【输出样例】 [1,#,2,3,#,4,5,7,#] 解题思路 利用宽度优先搜索完成本题 /*
// Definition for a Node.
class Node {public int val;public Node left;public Node right;public Node next;public Node() {}public Node(int _val) {val _val;}public Node(int _val, Node _left, Node _right, Node _next) {val _val;left _left;right _right;next _next;}
};
*/class Solution {public Node connect(Node root) {if(root null){return root;}//队列存储节点信息QueueNode queue new LinkedList();queue.add(root);while(!queue.isEmpty()){//每一层的数量int levelCount queue.size();//前一个节点Node pre null;for(int i0;ilevelCount;i){//出队Node node queue.poll();if(pre ! null){//不是第一个节点pre.next node;}pre node;//查看左右节点是否为空不空入队if(node.left ! null){queue.add(node.left);}if(node.right ! null){queue.add(node.right);}}}return root;}
} 时间 击败了76.40% 内存 击败了5.16%
