手机优化网站建设,权威发布型舆情回应以什么为主,广告推广是什么,网站开发如何让图片加载的更快一、513.找树左下角的值
这个题目的主要思路是使用广度优先搜索#xff08;BFS#xff09;遍历整棵树#xff0c;最后返回最后一层的最左边的节点的值。具体的实现可以使用队列来存储每一层的节点#xff0c;并且在遍历每一层节点时#xff0c;不断更新最左边的节点的值。…一、513.找树左下角的值
这个题目的主要思路是使用广度优先搜索BFS遍历整棵树最后返回最后一层的最左边的节点的值。具体的实现可以使用队列来存储每一层的节点并且在遍历每一层节点时不断更新最左边的节点的值。时间复杂度为O(n)其中n是节点的个数。
二、112.路径总和
这个题目的主要思路是使用深度优先搜索DFS遍历整棵树同时记录到达每个节点时的路径和如果到达叶子节点时路径和等于给定的目标和则返回true。具体的实现可以使用递归来实现DFS同时在每个节点处更新路径和并且在到达叶子节点时判断路径和是否等于目标和。时间复杂度为O(n)其中n是节点的个数。
三、113.路径总和ii
这个题目的主要思路和112题类似也是使用DFS遍历整棵树同时记录到达每个节点时的路径和并且在到达叶子节点时判断路径和是否等于给定的目标和。不同的是这个题目需要返回所有满足条件的路径而不仅仅是返回true或false。具体的实现可以在DFS的过程中使用一个数组来存储当前的路径并且在到达叶子节点时如果路径和等于目标和则将整个路径加入结果列表中。时间复杂度为O(n^2)其中n是节点的个数主要是因为每次需要复制一份路径数组。
四、106.从中序与后序遍历序列构造二叉树
这个题目的主要思路是使用递归来构建整棵树。具体的实现可以先找到后序遍历序列中的最后一个节点作为根节点然后在中序遍历序列中找到根节点的位置从而确定左子树和右子树的范围。然后递归的构建左子树和右子树即可。时间复杂度为O(n)其中n是节点的个数。
五、105.从前序与中序遍历序列构造二叉树
这个题目的主要思路和106题类似也是使用递归来构建整棵树。具体的实现可以先找到前序遍历序列中的第一个节点作为根节点然后在中序遍历序列中找到根节点的位置从而确定左子树和右子树的范围。然后递归的构建左子树和右子树即可。时间复杂度为O(n)其中n是节点的个数。
一、513.找树左下角的值
public int findBottomLeftValue(TreeNode root) {QueueTreeNode queue new LinkedList();queue.offer(root);int res root.val;while (!queue.isEmpty()) {int size queue.size();for (int i 0; i size; i) {TreeNode node queue.poll();if (i 0) {res node.val;}if (node.left ! null) {queue.offer(node.left);}if (node.right ! null) {queue.offer(node.right);}}}return res;
}二、112.路径总和
public boolean hasPathSum(TreeNode root, int sum) {if (root null) {return false;}if (root.left null root.right null) {return sum root.val;}return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
}三、113.路径总和ii
public ListListInteger pathSum(TreeNode root, int sum) {ListListInteger res new ArrayList();ListInteger path new ArrayList();dfs(root, sum, path, res);return res;
}private void dfs(TreeNode root, int sum, ListInteger path, ListListInteger res) {if (root null) {return;}path.add(root.val);if (root.left null root.right null sum root.val) {res.add(new ArrayList(path));}dfs(root.left, sum - root.val, path, res);dfs(root.right, sum - root.val, path, res);path.remove(path.size() - 1);
}四、106.从中序与后序遍历序列构造二叉树
public TreeNode buildTree(int[] inorder, int[] postorder) {if (inorder null || postorder null || inorder.length ! postorder.length) {return null;}int n inorder.length;MapInteger, Integer map new HashMap();for (int i 0; i n; i) {map.put(inorder[i], i);}return buildTree(inorder, 0, n - 1, postorder, 0, n - 1, map);
}private TreeNode buildTree(int[] inorder, int inStart, int inEnd, int[] postorder, int postStart, int postEnd, MapInteger, Integer map) {if (inStart inEnd || postStart postEnd) {return null;}int rootVal postorder[postEnd];TreeNode root new TreeNode(rootVal);int index map.get(rootVal);int leftSize index - inStart;root.left buildTree(inorder, inStart, index - 1, postorder, postStart, postStart leftSize - 1, map);root.right buildTree(inorder, index 1, inEnd, postorder, postStart leftSize, postEnd - 1, map);return root;
}五、105.从前序与中序遍历序列构造二叉树
public TreeNode buildTree(int[] preorder, int[] inorder) {if (preorder null || inorder null || preorder.length ! inorder.length) {return null;}int n preorder.length;MapInteger, Integer map new HashMap();for (int i 0; i n; i) {map.put(inorder[i], i);}return buildTree(preorder, 0, n - 1, inorder, 0, n - 1, map);
}private TreeNode buildTree(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd, MapInteger, Integer map) {if (preStart preEnd || inStart inEnd) {return null;}int rootVal preorder[preStart];TreeNode root new TreeNode(rootVal);int index map.get(rootVal);int leftSize index - inStart;root.left buildTree(preorder, preStart 1, preStart leftSize, inorder, inStart, index - 1, map);root.right buildTree(preorder, preStart leftSize 1, preEnd, inorder, index 1, inEnd, map);return root;
}
