第六章 二叉树part04今日内容： ● 110.平衡二叉树
● 257. 二叉树的所有路径
● 404.左叶子之和 详细布置 迭代法，大家可以直接过，二刷有精力的时候 再去掌握迭代法。110.平衡二叉树 （优先掌握递归）再一次涉及到，什么是高度，什么是深度，可以巩固一下。题目链接/文章讲解/视频讲解：https://programmercarl.com/0110.%E5%B9%B3%E8%A1%A1%E4%BA%8C%E5%8F%89%E6%A0%91.html 257. 二叉树的所有路径 （优先掌握递归） 这是大家第一次接触到回溯的过程， 我在视频里重点讲解了 本题为什么要有回溯，已经回溯的过程。 如果对回溯 似懂非懂，没关系， 可以先有个印象。 题目链接/文章讲解/视频讲解：https://programmercarl.com/0257.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E6%89%80%E6%9C%89%E8%B7%AF%E5%BE%84.html 404.左叶子之和 （优先掌握递归）其实本题有点文字游戏，搞清楚什么是左叶子，剩下的就是二叉树的基本操作。 题目链接/文章讲解/视频讲解：https://programmercarl.com/0404.%E5%B7%A6%E5%8F%B6%E5%AD%90%E4%B9%8B%E5%92%8C.html 往日任务
● day 1 任务以及具体安排：https://docs.qq.com/doc/DUG9UR2ZUc3BjRUdY
● day 2 任务以及具体安排：https://docs.qq.com/doc/DUGRwWXNOVEpyaVpG
● day 3 任务以及具体安排：https://docs.qq.com/doc/DUGdqYWNYeGhlaVR6
● day 4 任务以及具体安排：https://docs.qq.com/doc/DUFNjYUxYRHRVWklp
● day 5 周日休息
● day 6 任务以及具体安排：https://docs.qq.com/doc/DUEtFSGdreWRuR2p4
● day 7 任务以及具体安排：https://docs.qq.com/doc/DUElCb1NyTVpXa0Jj
● day 8 任务以及具体安排：https://docs.qq.com/doc/DUGdsY2JFaFhDRVZH
● day 9 任务以及具体安排：https://docs.qq.com/doc/DUHVXSnZNaXpVUHN4
● day 10 任务以及具体安排：https://docs.qq.com/doc/DUElqeHh3cndDbW1Q
●day 11 任务以及具体安排：https://docs.qq.com/doc/DUHh6UE5hUUZOZUd0
●day 12 周日休息
●day 13 任务以及具体安排：https://docs.qq.com/doc/DUHNpa3F4b2dMUWJ3
●day 14 任务以及具体安排：https://docs.qq.com/doc/DUHRtdXZZSWFkeGdE
●day 15 任务以及具体安排：https://docs.qq.com/doc/DUHN0ZVJuRmVYeWNv
●day 16 任务以及具体安排：https://docs.qq.com/doc/DUHBQRm1aSWR4T2NK目录
0110_平衡二叉树
0257_二叉树的所有路径
0404_左叶子之和
0110_平衡二叉树
java">class Solution0110_2 {/*** 递归法*/public boolean isBalanced(TreeNode root) {return getHeight(root) != -1;}private int getHeight(TreeNode root) {if (root == null) {return 0;}int leftHeight = getHeight(root.left);if (leftHeight == -1) {return -1;}int rightHeight = getHeight(root.right);if (rightHeight == -1) {return -1;}//左右子树高度差大于1，return -1表示已经不是平衡树了if (Math.abs(leftHeight - rightHeight) > 1) {return -1;}return Math.max(leftHeight, rightHeight) + 1;}
}0257_二叉树的所有路径
java">package com.question.solve.leetcode.programmerCarl2._07_binaryTrees;import javax.print.attribute.standard.NumberUp;
import java.nio.file.Paths;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;public class _0257_二叉树的所有路径 {
}/*** 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 Solution0257 {//解法一：方式一/*** 递归法*/public List<String> binaryTreePaths(TreeNode root) {List<String> res = new ArrayList<>();//存最终的结果if (root == null) {return res;}List<Integer> paths = new ArrayList<>();//作为结果中的路径traversal(root, paths, res);return res;}private void traversal(TreeNode root, List<Integer> paths, List<String> res) {paths.add(root.val);//前序遍历，中//遇到叶子结点if (root.left == null && root.right == null) {//输出StringBuilder sb = new StringBuilder();//StringBuilder用来拼接字符串，速度更快for (int i = 0; i < paths.size() - 1; i++) {sb.append(paths.get(i)).append("->");}sb.append(paths.get(paths.size() - 1));//记录最后一个节点res.add(sb.toString());//收集一个路径return;}//递归和回溯是同时进行，所以要放在同一个花括号里if (root.left != null) { //左traversal(root.left, paths, res);paths.remove(paths.size() - 1);//回溯}if (root.right != null) { //右traversal(root.right, paths, res);paths.remove(paths.size() - 1);//回溯}}
}class Solution0257_2 {//解法一：方式二List<String> result = new ArrayList<>();public List<String> binaryTreePaths(TreeNode root) {deal(root, "");return result;}public void deal(TreeNode node, String s) {if (node == null)return;if (node.left == null && node.right == null) {result.add(new StringBuilder(s).append(node.val).toString());return;}String tmp = new StringBuilder(s).append(node.val).append("->").toString();deal(node.left, tmp);deal(node.right, tmp);}
}class Solution0257_3 {//解法二/*** 迭代法*/public List<String> binaryTreePaths(TreeNode root) {List<String> result = new ArrayList<>();if (root == null)return result;Stack<Object> stack = new Stack<>();//节点和路径同时入栈stack.push(root);stack.push(root.val + "");while (!stack.isEmpty()) {//节点和路径同时出栈String path = (String) stack.pop();TreeNode node = (TreeNode) stack.pop();// 若找到叶子节点if (node.left == null && node.right == null) {result.add(path);}//右子节点不为空if (node.right != null) {stack.push(node.right);stack.push(path + "->" + node.right.val);}//左子节点不为空if (node.left != null) {stack.push(node.left);stack.push(path + "->" + node.left.val);}}return result;}
}0404_左叶子之和
java">package com.question.solve.leetcode.programmerCarl2._07_binaryTrees;import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;public class _0404_左叶子之和 {
}/*** 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 sumOfLeftLeaves(TreeNode root) {int sum = 0;if (root == null || (root.left == null && root.right == null)) {return sum;}Deque<TreeNode> deque = new LinkedList<TreeNode>();deque.offer(root);while (!deque.isEmpty()) {int size = deque.size();for (int i = 0; i < size; i++) {TreeNode poll = deque.poll();if (poll.left != null && poll.left.left == null && poll.left.right == null) {sum += poll.left.val;}if (poll.left != null) {deque.offer(poll.left);}if (poll.right != null) {deque.offer(poll.right);}}}return sum;}public int sumOfLeftLeaves2(TreeNode root) {//递归if (root == null) return 0;int leftValue = sumOfLeftLeaves(root.left); //左int rightValue = sumOfLeftLeaves(root.right); //右int midValue = 0;if (root.left != null && root.left.left == null && root.left.right == null) {midValue = root.left.val;}int sum = midValue + leftValue + rightValue; //中return sum;}public int sumOfLeftLeaves3(TreeNode root) {//迭代if (root == null) return 0;Stack<TreeNode> stack = new Stack<>();stack.add(root);int result = 0;while (!stack.isEmpty()) {TreeNode node = stack.pop();if (node.left != null && node.left.left == null && node.left.right == null) {result += node.left.val;}if (node.right != null) stack.add(node.right);if (node.left != null) stack.add(node.left);}return result;}public int sumOfLeftLeaves4(TreeNode root) {//层序遍历迭代法int sum = 0;if (root == null) return 0;Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);while (!queue.isEmpty()) {int size = queue.size();while (size-- > 0) {TreeNode node = queue.poll();if (node.left != null) {//左节点不为空queue.offer(node.left);if (node.left.left == null && node.left.right == null) { // 左叶子节点sum += node.left.val;}}if (node.right != null) queue.offer(node.right);}}return sum;}
}
