力扣labuladong——一刷day43

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

---

前言

---

一般来说，如果让你在二叉树的「树枝」上做文章，那么用遍历的思维模式解题是比较自然的想法

一、力扣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 {List<String> res = new ArrayList<>();List<Integer> path = new ArrayList<>();public List<String> 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 {Deque<TreeNode> deq = new LinkedList<>();public List<Integer> rightSideView(TreeNode root) {List<Integer> 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;List<Integer> res = new ArrayList<>();public List<Integer> 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*i+1，层序遍历时记录每层第一个和最后一个元素的序号，即可得出本层的宽度

/*** 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;}Deque<Pair> 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*2+1));}}res = Math.max(res,(high-low+1));}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 {List<Integer> 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, depth+1, id*2);fun(root.right, depth+1, id*2+1);}
}