代码随想录算法训练营第十七天| 110.平衡二叉树、 257. 二叉树的所有路径、 ...

110.平衡二叉树

   题目链接：110.平衡二叉树
文档讲讲：代码随想录
状态：还可以
  思路：计算左右子树的深度差，递归判断左右子树是否符合平衡条件
题解：

1.     public boolean isBalanced(TreeNode root) {
2.         if (root == null) {
3.             return true;
4.         }
5.         int leftLen = getMaxLen(root.left);
6.         int rightLen = getMaxLen(root.right);
8.         return Math.abs(leftLen - rightLen) <= 1 && isBalanced(root.left) && isBalanced(root.right);
9.     }
11.     public int getMaxLen(TreeNode node) {
12.         if (node == null) {
13.             return 0;
14.         }
15.         int leftLen = getMaxLen(node.left);
16.         int rightLen = getMaxLen(node.right);
17.         return Math.max(leftLen, rightLen) + 1;
18.     }

复制代码

257. 二叉树的所有路径

   题目链接： 257. 二叉树的所有路径
文档讲解：代码随想录
状态：没写出来
  思路：前序+回溯的思路，遇到叶子节点收集路径
递归解法：

1.     public List<String> binaryTreePaths(TreeNode root) {
2.         List<String> res = new LinkedList<>();
3.         StringBuilder sb = new StringBuilder();
4.         getPath(root, res, sb);
5.         return res;
6.     }
8.     public void getPath(TreeNode root, List<String> res, StringBuilder sb) {
9.         if (root == null) {
10.             return;
11.         }
12.         int length = sb.length();
13.         sb.append(root.val);
14.         if (root.left == null && root.right == null) {
15.             res.add(sb.toString());
16.         } else {
17.             sb.append("->");
18.             getPath(root.left, res, sb);
19.             getPath(root.right, res, sb);
20.         }
21.         sb.setLength(length); // 恢复StringBuilder的状态
22.     }

复制代码

迭代解法：

1.     public List<String> binaryTreePaths(TreeNode root) {
2.         List<String> res = new LinkedList<>();
3.         if (root == null) {
4.             return res;
5.         }
7.         // 创建双端队列来存储节点和路径
8.         Deque<TreeNode> deque = new LinkedList<>();
9.         Deque<String> pathDeque = new LinkedList<>();
11.         // 初始节点和路径
12.         deque.addLast(root);
13.         pathDeque.addLast(Integer.toString(root.val));
15.         while (!deque.isEmpty()) {
16.             TreeNode node = deque.pollLast();
17.             String path = pathDeque.pollLast();
18.             // 如果当前节点是叶子节点，将路径添加到结果中
19.             if (node.left == null && node.right == null) {
20.                 res.add(path);
21.             }
22.             // 如果右子节点不为空，添加到队列中并更新路径
23.             if (node.right != null) {
24.                 deque.addLast(node.right);
25.                 pathDeque.addLast(path + "->" + node.right.val);
26.             }
27.             // 如果左子节点不为空，添加到队列中并更新路径
28.             if (node.left != null) {
29.                 deque.addLast(node.left);
30.                 pathDeque.addLast(path + "->" + node.left.val);
31.             }
32.         }
34.         return res;
35.     }

复制代码

404.左叶子之和

   题目链接： 404.左叶子之和
文档讲解：代码随想录
状态：总以为本身递归的思路对的，但是结果就是不对，原来是代码中笔误把root.left.right写成了root.right.right。。。。
  递归题解：

1.     public int sumOfLeftLeaves(TreeNode root) {
2.         // 如果根节点为空，返回0
3.         if (root == null) {
4.             return 0;
5.         }
7.         // 检查当前节点的左子节点是否为叶子节点
8.         if (root.left != null && root.left.left == null && root.left.right == null) {
9.             // 如果左子节点是叶子节点，返回左叶子节点的值，加上左子树和右子树的左叶子节点值
10.             return root.left.val + sumOfLeftLeaves(root.left) + sumOfLeftLeaves(root.right);
11.         } else {
12.             // 如果左子节点不是叶子节点，递归遍历左子树和右子树
13.             return sumOfLeftLeaves(root.left) + sumOfLeftLeaves(root.right);
14.         }
15.     }

复制代码

迭代题解：

1.     public int sumOfLeftLeaves(TreeNode root) {
2.         if (root == null) {
3.             return 0;
4.         }
5.         int sum = 0;
6.         Deque<TreeNode> deque = new LinkedList<>();
7.         deque.addLast(root);
8.         while (!deque.isEmpty()) {
9.             int size = deque.size();
10.             while (size-- > 0) {
11.                 TreeNode node = deque.pollFirst();
12.                 if (node.left != null) {
13.                     if (node.left.left == null && node.left.right == null) {
14.                         sum += node.left.val;
15.                     }
16.                     deque.addLast(node.left);
17.                 }
18.                 if (node.right != null) {
19.                     deque.addLast(node.right);
20.                 }
21.             }
22.         }
23.         return sum;
24.     }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。