网站制作模板教案,外贸英文网站建设价格,一键制作网页,风险网站怎么解决方法提示#xff1a;文章写完后#xff0c;目录可以自动生成#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、力扣257. 二叉树的所有路径二、力扣129. 求根节点到叶节点数字之和三、力扣199. 二叉树的右视图四、力扣662. 二叉树最大宽度 前言 一般来说#xff0c;如… 提示文章写完后目录可以自动生成如何生成可参考右边的帮助文档 文章目录 前言一、力扣257. 二叉树的所有路径二、力扣129. 求根节点到叶节点数字之和三、力扣199. 二叉树的右视图四、力扣662. 二叉树最大宽度 前言 一般来说如果让你在二叉树的「树枝」上做文章那么用遍历的思维模式解题是比较自然的想法
一、力扣257. 二叉树的所有路径
/*** 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 {ListString res new ArrayList();ListInteger path new ArrayList();public ListString binaryTreePaths(TreeNode root) {fun(root);return res;}public void fun(TreeNode root){if(root null){return;}if(root.left null root.right null){StringBuilder sb new StringBuilder();for(int i 0; i path.size();i ){sb.append(path.get(i)).append(-);}sb.append(root.val);res.add(sb.toString());return;}path.add(root.val);fun(root.left);fun(root.right);path.remove(path.size()-1);}
}二、力扣129. 求根节点到叶节点数字之和
/*** 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 {int sum 0, path 0;public int sumNumbers(TreeNode root) {fun(root);return sum;}public void fun(TreeNode root){if(root null){return;}if(root.left null root.right null){path (path * 10 root.val);System.out.println(path);sum path;path / 10;return;}path (path * 10 root.val);fun(root.left);fun(root.right);path / 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 {int sum 0;StringBuilder sb new StringBuilder();public int sumNumbers(TreeNode root) {fun(root);return sum;}public void fun(TreeNode root){if(root null){return;}sb.append(root.val);if(root.left null root.right null){sum Integer.parseInt(sb.toString());sb.deleteCharAt(sb.length()-1);return;}fun(root.left);fun(root.right);sb.deleteCharAt(sb.length()-1);}
}三、力扣199. 二叉树的右视图
层序遍历
/*** 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 {DequeTreeNode deq new LinkedList();public ListInteger rightSideView(TreeNode root) {ListInteger res new LinkedList();if(root null){return res;}deq.offerLast(root);while(!deq.isEmpty()){int len deq.size();TreeNode temp deq.peekLast();res.add(temp.val);for(int i 0; i len; i ){TreeNode cur deq.pollFirst();if(cur.left ! null){deq.offerLast(cur.left);}if(cur.right ! null){deq.offerLast(cur.right);}}}return res;}
}深度优先搜索
/*** 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 {int depth 0;ListInteger res new ArrayList();public ListInteger rightSideView(TreeNode root) {fun(root);return res;}public void fun(TreeNode root){if(root null){return;}depth ;if(depth res.size()){res.add(root.val);}fun(root.right);fun(root.left);depth --;}
}四、力扣662. 二叉树最大宽度
层序遍历采用完全二叉树的编号顺序给二叉树编号当前节点为i左孩子为2*i右孩子为2*i1层序遍历时记录每层第一个和最后一个元素的序号即可得出本层的宽度
/*** 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 {class Pair{TreeNode node;int id;public Pair(TreeNode node, int id){this.node node;this.id id;}}public int widthOfBinaryTree(TreeNode root) {if(root null){return 0;}DequePair deq new LinkedList();deq.offerLast(new Pair(root,1));int res 0;while(!deq.isEmpty()){int len deq.size();int low 0, high 0;for(int i 0; i len; i ){Pair temp deq.pollFirst();TreeNode cur temp.node;int curId temp.id;if(i 0){low curId;}if(i len - 1){high curId;}if(cur.left ! null){deq.offerLast(new Pair(cur.left,curId*2));}if(cur.right ! null){deq.offerLast(new Pair(cur.right,curId*21));}}res Math.max(res,(high-low1));}return res;}
}DFS方式,采用一个List集合记录左侧第一个节点的id使用depth和List集合的长度控制层数当第一次进入某一层时List的长度只能是depth-1才是第一个左孩子左孩子一旦加入List的长度就等于depth了此时同一层的其他节点就不会加入集合了那么遍使用其他节点减去本层第一个左孩子来更新本层宽度
/*** 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 {ListInteger list new ArrayList();int res 1;public int widthOfBinaryTree(TreeNode root) {if(root null){return 0;} fun(root, 1, 1);return res;}public void fun(TreeNode root, int depth, int id){if(root null){return;}if(depth - 1 list.size()){list.add(id);}else{res Math.max(res, id - list.get(depth-1) 1);}fun(root.left, depth1, id*2);fun(root.right, depth1, id*21);}
}
