网站制作需要的材料/网络营销软文范例大全800

Leetcode剑指Offer刷题指南：

Leetcode剑指Offer刷题-学习计划目录_DEGv587的博客-CSDN博客

剑指 Offer 34. 二叉树中和为某一值的路径 

解法：DFS（先序遍历 + 路径记录）LinkedList

/*初始化：构建 ret ，路径列表pathpathSum(root, target) 函数：1.dfs；2.返回ret；dfs(node, target) 函数：1.递推参数：当前节点 node，目标和 target2.终止条件：当前节点为空，直接返回3.递推：1）路径更新：将当前节点值 node.val 加入路径 path；2）目标和更新：target -= node.val;3）路径记录：当 node 为叶子节点 且 路径和为目标和 时，记录此路径 path 加入 ret；4）路径恢复：向上回溯前，需要将当前节点从路径 path 中删除，即 path.pop()*/
class Solution {LinkedList<List<Integer>> ret = new LinkedList<>();LinkedList<Integer> path = new LinkedList<>();public List<List<Integer>> pathSum(TreeNode root, int target) {//1.dfs；dfs(root, target);//2.返回ret；return ret;}private void dfs(TreeNode node, int target) {//终止条件：当前节点为空，直接返回if (node == null) {return;}//递推 - 先序遍历（根、左、右）：//1）路径更新：将当前节点值 node.val 加入路径 path；path.add(node.val);//2）目标和更新：target -= node.val;target -= node.val;//3）路径记录：当 node 为叶子节点 且 路径和为目标和 时，记录此路径 path 加入 ret；if (node.left == null && node.right == null && target == 0) {ret.add(new LinkedList(path));}dfs(node.left, target);dfs(node.right, target);//4）路径恢复：向上回溯前，需要将当前节点从路径 path 中删除，即 path.pop()path.removeLast();}
}

DFS（先序遍历 + 路径记录）ArrayList

class Solution {private List<List<Integer>> ret = new ArrayList<>();public List<List<Integer>> pathSum(TreeNode root, int target) {dfs(root, target, new ArrayList<>());return ret;}private void dfs(TreeNode node, int target, List<Integer> path) {if (node == null) {return;}path.add(node.val);target -= node.val;if (node.left == null && node.right == null && target == 0) {ret.add(new ArrayList(path));}dfs(node.left, target, path);dfs(node.right, target, path);path.remove(path.size() - 1);}
}

剑指 Offer 36. 二叉搜索树与双向链表

解法：dfs 中序遍历

class Solution {Node head, pre;public Node treeToDoublyList(Node root) {if (root == null) return null;dfs(root);//进行头节点和尾节点的相互指向 - 形成双向pre.right = head;head.left = pre;return head;}public void dfs(Node cur) {if (cur == null) return;dfs(cur.left);//pre用于记录双向链表中位于cur左侧的节点，即上一次迭代中的cur,当pre==null时，cur左侧没有节点,即此时cur为双向链表中的头节点if (pre == null) {head = cur;} else {//反之，pre!=null时，cur左侧存在节点pre，需要进行pre.right=cur的操作。pre.right = cur;}//pre是否为null对这句没有影响,且这句放在上面两句if else之前也是可以的。cur.left = pre;//pre指向当前的curpre = cur;//全部迭代完成后，pre指向双向链表中的尾节点dfs(cur.right);}
}

剑指 Offer 54. 二叉搜索树的第k大节点

解法：中序遍历 + 辅助存储

class Solution {private int ret = 0, count = 0;public int kthLargest(TreeNode root, int k) {if (root == null) return 0;midDfs(root, k);return ret;}private void midDfs(TreeNode root, int k) {//中序（右、根、左）if (root.right != null) {midDfs(root.right, k);}if (++count == k) {ret = root.val;return;}if (root.left != null) {midDfs(root.left, k);}}
}