河间做网站 申梦网络,网页设计软件h,互联免费主机,wordpress商城制作教程LeetCode#xff1a;513.找树左下角的值
解决方案#xff1a;
1.思路
在遍历一个节点时#xff0c;需要先把它的非空右子节点放入队列#xff0c;然后再把它的非空左子节点放入队列#xff0c;这样才能保证从右到左遍历每一层的节点。广度优先搜索所遍历的最后一个节点…LeetCode513.找树左下角的值
解决方案
1.思路
在遍历一个节点时需要先把它的非空右子节点放入队列然后再把它的非空左子节点放入队列这样才能保证从右到左遍历每一层的节点。广度优先搜索所遍历的最后一个节点的值就是最底层最左边节点的值。
class Solution {public int findBottomLeftValue(TreeNode root) {int ret 0;//基于数组的双端队列QueueTreeNode queue new ArrayDequeTreeNode();queue.offer(root);while (!queue.isEmpty()) {TreeNode p queue.poll();if (p.right ! null) {queue.offer(p.right);}if (p.left ! null) {queue.offer(p.left);}//如果当前队列不为空。当前根节点既没有左节点也没有右节点那么就把此该节点赋值给retret p.val;}return ret;}
}3.复杂度分析
LeetCode112. 路径总和
解决方案
1.思路
递归三部曲
函数返回类型和参数终止条件递归逻辑
递归逻辑
2.代码实现
public class Solution {private boolean traversal(TreeNode cur, int count) {if (cur.left null cur.right null count 0) return true; // 遇到叶子节点并且计数为0if (cur.left null cur.right null) return false; // 遇到叶子节点直接返回if (cur.left ! null) { // 左count - cur.left.val; // 递归处理节点;if (traversal(cur.left, count)) return true;count cur.left.val; // 回溯撤销处理结果}if (cur.right ! null) { // 右count - cur.right.val; // 递归处理节点;if (traversal(cur.right, count)) return true;count cur.right.val; // 回溯撤销处理结果}return false;}public boolean hasPathSum(TreeNode root, int sum) {if (root null) return false;return traversal(root, sum - root.val);}
}3.复杂度分析 LeetCode113.路径总和ii
解决方案
1.思路
思路同112但是注意递归函数不再有返回值而是用一个 path数组接住然后再用一个result数组接住所有path
2.代码实现
public class Solution {private ListListInteger result new ArrayList();private ListInteger path new ArrayList();// 递归函数不需要返回值因为我们要遍历整个树private void traversal(TreeNode cur, int count) {if (cur.left null cur.right null count 0) { // 遇到了叶子节点且找到了和为sum的路径result.add(new ArrayList(path));return;}if (cur.left null cur.right null) return; // 遇到叶子节点而没有找到合适的边直接返回if (cur.left ! null) { // 左 空节点不遍历path.add(cur.left.val);count - cur.left.val;traversal(cur.left, count); // 递归count cur.left.val; // 回溯path.remove(path.size() - 1); // 回溯}if (cur.right ! null) { // 右 空节点不遍历path.add(cur.right.val);count - cur.right.val;traversal(cur.right, count); // 递归count cur.right.val; // 回溯path.remove(path.size() - 1); // 回溯}}public ListListInteger pathSum(TreeNode root, int sum) {result.clear();path.clear();if (root null) return result;path.add(root.val); // 把根节点放进路径traversal(root, sum - root.val);return result;}
}3.复杂度分析
时间复杂度O(N)其中N是树中节点的数量。这是因为每个节点在递归过程中会被访问一次。尽管存在递归调用但每个节点只被访问并处理一次因此总体时间复杂度线性依赖于树的大小而不是递归深度。空间复杂度最坏情况下当树完全不平衡且每一条从根到叶子的路径都满足题目条件时递归的深度达到最大此时的空间复杂度由递归栈的深度决定为O(N)。最好情况下即树完全平衡递归的最大深度为log(N)因此在这种情况下空间复杂度为O(log(N))。但由于我们还需要存储路径path在最坏情况下每条边都构成解这也会占用O(N)的空间。因此综合考虑整体的空间复杂度也是O(N)。
LeetCode106.从中序与后序遍历序列构造二叉树
解决方案
1.思路
利用遍历特性中序遍历左根右确定节点在序列中的相对位置后序遍历左右根的最后一个元素总是当前子树的根节点递归思想通过递归不断地将问题分解为更小的子问题直到达到基础情况空列表然后逐层返回逐步构建整棵树。动态调整遍历列表每次递归调用前根据当前子树的信息调整中序和后序遍历列表确保传入的列表仅对应当前子树的信息。
2.代码实现
import java.util.ArrayList;
import java.util.List;public class Solution {private TreeNode traversal(ListInteger inorder, ListInteger postorder) {if (postorder.size() 0) return null;// 后序遍历数组最后一个元素就是当前的中间节点int rootValue postorder.get(postorder.size() - 1);TreeNode root new TreeNode(rootValue);// 叶子节点if (postorder.size() 1) return root;// 找到中序遍历的切割点int delimiterIndex;for (delimiterIndex 0; delimiterIndex inorder.size(); delimiterIndex) {if (inorder.get(delimiterIndex) rootValue) break;}// 切割中序数组ListInteger leftInorder new ArrayList(inorder.subList(0, delimiterIndex));ListInteger rightInorder new ArrayList(inorder.subList(delimiterIndex 1, inorder.size()));// postorder 舍弃末尾元素postorder.remove(postorder.size() - 1);// 切割后序数组ListInteger leftPostorder new ArrayList(postorder.subList(0, leftInorder.size()));ListInteger rightPostorder new ArrayList(postorder.subList(leftInorder.size(), postorder.size()));root.left traversal(leftInorder, leftPostorder);root.right traversal(rightInorder, rightPostorder);return root;}public TreeNode buildTree(ListInteger inorder, ListInteger postorder) {if (inorder.size() 0 || postorder.size() 0) return null;return traversal(inorder, postorder);}
}3.复杂度分析
时间复杂度尽管递归深度会影响栈的空间复杂度但从时间复杂度的角度看每个节点都会导致一次遍历操作和一次分割操作总的时间复杂度与树中节点数量成正比即O(n)。这里的n代表树中节点的总数。空间复杂度该算法的时间复杂度为O(n)空间复杂度在最坏情况下也是O(n)主要是由于递归调用栈的深度可能达到O(n)。在实际应用中若二叉树较为平衡空间复杂度可以视为O(log n)
