响应网官方网站,网站建设专业总结,做网单哪个网站最好用,网站开发人员 生活110.平衡二叉树 题目链接#xff1a;110.平衡二叉树 文档讲讲#xff1a;代码随想录 状态#xff1a;还可以 思路#xff1a;计算左右子树的深度差#xff0c;递归判断左右子树是否符合平衡条件
题解#xff1a; public boolean isBalanced(TreeNode root) {if (root n…110.平衡二叉树 题目链接110.平衡二叉树 文档讲讲代码随想录 状态还可以 思路计算左右子树的深度差递归判断左右子树是否符合平衡条件
题解 public boolean isBalanced(TreeNode root) {if (root null) {return true;}int leftLen getMaxLen(root.left);int rightLen getMaxLen(root.right);return Math.abs(leftLen - rightLen) 1 isBalanced(root.left) isBalanced(root.right);}public int getMaxLen(TreeNode node) {if (node null) {return 0;}int leftLen getMaxLen(node.left);int rightLen getMaxLen(node.right);return Math.max(leftLen, rightLen) 1;}257. 二叉树的所有路径 题目链接 257. 二叉树的所有路径 文档讲解代码随想录 状态没写出来 思路前序回溯的思路遇到叶子节点收集路径
递归解法 public ListString binaryTreePaths(TreeNode root) {ListString res new LinkedList();StringBuilder sb new StringBuilder();getPath(root, res, sb);return res;}public void getPath(TreeNode root, ListString res, StringBuilder sb) {if (root null) {return;}int length sb.length();sb.append(root.val);if (root.left null root.right null) {res.add(sb.toString());} else {sb.append(-);getPath(root.left, res, sb);getPath(root.right, res, sb);}sb.setLength(length); // 恢复StringBuilder的状态}迭代解法 public ListString binaryTreePaths(TreeNode root) {ListString res new LinkedList();if (root null) {return res;}// 创建双端队列来存储节点和路径DequeTreeNode deque new LinkedList();DequeString pathDeque new LinkedList();// 初始节点和路径deque.addLast(root);pathDeque.addLast(Integer.toString(root.val));while (!deque.isEmpty()) {TreeNode node deque.pollLast();String path pathDeque.pollLast();// 如果当前节点是叶子节点将路径添加到结果中if (node.left null node.right null) {res.add(path);}// 如果右子节点不为空添加到队列中并更新路径if (node.right ! null) {deque.addLast(node.right);pathDeque.addLast(path - node.right.val);}// 如果左子节点不为空添加到队列中并更新路径if (node.left ! null) {deque.addLast(node.left);pathDeque.addLast(path - node.left.val);}}return res;}
404.左叶子之和 题目链接 404.左叶子之和 文档讲解代码随想录 状态总觉得自己递归的思路对的但是结果就是不对原来是代码中笔误把root.left.right写成了root.right.right。。。。 递归题解 public int sumOfLeftLeaves(TreeNode root) {// 如果根节点为空返回0if (root null) {return 0;}// 检查当前节点的左子节点是否为叶子节点if (root.left ! null root.left.left null root.left.right null) {// 如果左子节点是叶子节点返回左叶子节点的值加上左子树和右子树的左叶子节点值return root.left.val sumOfLeftLeaves(root.left) sumOfLeftLeaves(root.right);} else {// 如果左子节点不是叶子节点递归遍历左子树和右子树return sumOfLeftLeaves(root.left) sumOfLeftLeaves(root.right);}}迭代题解 public int sumOfLeftLeaves(TreeNode root) {if (root null) {return 0;}int sum 0;DequeTreeNode deque new LinkedList();deque.addLast(root);while (!deque.isEmpty()) {int size deque.size();while (size-- 0) {TreeNode node deque.pollFirst();if (node.left ! null) {if (node.left.left null node.left.right null) {sum node.left.val;}deque.addLast(node.left);}if (node.right ! null) {deque.addLast(node.right);}}}return sum;}
