查网站是否正规,wordpress给指定用户设置角色,珠海门户网站建设哪家专业,深圳市住房和建设局工程交易平台废话不多说#xff0c;喊一句号子鼓励自己#xff1a;程序员永不失业#xff0c;程序员走向架构#xff01;本篇Blog的主题是【遍历求和】#xff0c;使用【二叉树】这个基本的数据结构来实现#xff0c;这个高频题的站点是#xff1a;CodeTop#xff0c;筛选条件为喊一句号子鼓励自己程序员永不失业程序员走向架构本篇Blog的主题是【遍历求和】使用【二叉树】这个基本的数据结构来实现这个高频题的站点是CodeTop筛选条件为目标公司最近一年出现频率排序由高到低的去牛客TOP101去找只有两个地方都出现过才做这道题CodeTop本身汇聚了LeetCode的来源确保刷的题都是高频要面试考的题。 明确目标题后附上题目链接后期可以依据解题思路反复快速练习题目按照题干的基本数据结构分类且每个分类的第一篇必定是对基础数据结构的介绍。
求根到叶子节点数字之和【MID】
DFS和BFS两种做法
题干
直接粘题干和用例
解题思路
原题解地址这道题中二叉树的每条从根节点到叶子节点的路径都代表一个数字。其实每个节点都对应一个数字等于其父节点对应的数字乘以 10 再加上该节点的值这里假设根节点的父节点对应的数字是 0。只要计算出每个叶子节点对应的数字然后计算所有叶子节点对应的数字之和即可得到结果。可以通过深度优先搜索和广度优先搜索实现。
深度优先搜索DFS
深度优先搜索是很直观的做法。从根节点开始遍历每个节点如果遇到叶子节点则将叶子节点对应的数字加到数字之和。如果当前节点不是叶子节点则计算其子节点对应的数字然后对子节点递归遍历
广度优先搜索BFS
使用广度优先搜索需要维护两个队列分别存储节点和节点对应的数字。
初始时将根节点和根节点的值分别加入两个队列。每次从两个队列分别取出一个节点和一个数字进行如下操作 如果当前节点是叶子节点则将该节点对应的数字加到数字之和如果当前节点不是叶子节点则获得当前节点的非空子节点并根据当前节点对应的数字和子节点的值计算子节点对应的数字然后将子节点和子节点对应的数字分别加入两个队列。
搜索结束后即可得到所有叶子节点对应的数字之和。 按照数值队列顺序加上了节点对应的值
代码实现
分别用DFS和BFS实现
DFS代码实现
给出代码实现基本档案 基本数据结构二叉树 辅助数据结构无 算法递归 技巧无 其中数据结构、算法和技巧分别来自
10 个数据结构数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie 树10 个算法递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法技巧双指针、滑动窗口、中心扩散
当然包括但不限于以上
/*** 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 {public int sumNumbers(TreeNode root) {return dfsSum(root, 0);}private int dfsSum(TreeNode node, int preIndex) {// 1 递归终止越过叶子节点返回0;if (node null) {return 0;}// 2 计算到当前节点的数值int curValue preIndex * 10 node.val;// 3 判断当前节点是否为叶子节点,到叶子节点则返回叶子节点值非叶子节点的和为左右子节点的和if (node.left null node.right null) {return curValue;} else {return dfsSum(node.left, curValue) dfsSum(node.right, curValue);}}
}BFS代码实现
给出代码实现基本档案 基本数据结构二叉树 辅助数据结构队列 算法迭代 技巧无 其中数据结构、算法和技巧分别来自
10 个数据结构数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie 树10 个算法递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法技巧双指针、滑动窗口、中心扩散
/*** 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 {public int sumNumbers(TreeNode root) {// 1 入参判断如果root为空返回0if (root null) {return 0;}// 2 定义两个队列一个为节点队列一个为 节点值队列用于存放当前节点为止的数字QueueTreeNode nodeQueue new LinkedListTreeNode();QueueInteger numQueue new LinkedListInteger();nodeQueue.offer(root);numQueue.offer(root.val);// 3 借助队列进行层次遍历int sum 0;while (!nodeQueue.isEmpty()) {// 3-1 处理队头元素,获取节点和截止当前节点的数值TreeNode curNode nodeQueue.poll();int curValue numQueue.poll();if (curNode.left null curNode.right null) {// 到了叶子节点则只剩下节点值累加即可sum curValue;} else {// 如果左子节点不为空则将左子节点入队并且更新左子节点的截止数值if (curNode.left ! null) {nodeQueue.offer(curNode.left);numQueue.offer(curValue * 10 curNode.left.val);}// 如果右子节点不为空则将右子节点入队并且更新右子节点的截止数值if (curNode.right ! null) {nodeQueue.offer(curNode.right);numQueue.offer(curValue * 10 curNode.right.val);}}}return sum ;}}复杂度分析
时间复杂度O(N)。遍历了一遍二叉树时间复杂度为ON空间复杂度O(N)。DFS时 递归最差情况下时间复杂度为ONBFS时队列占用空间ON
