【算法刷题day17】Leetcode:110.平衡二叉树、257. 二叉树的所有路径、404.左叶子之和

草稿图网站
java的Deque

Leetcode 110.平衡二叉树

题目：** 110.平衡二叉树**
解析：代码随想录解析

解题思路

求高度的方法加一点判断

代码

/*** 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;*     }* }*///使用求高度来代替，使用-1来减枝
class Solution {public boolean isBalanced(TreeNode root) {return getHeight(root) != -1;}public 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;if (Math.abs(leftHeight-rightHeight) > 1)return -1;return Math.max(leftHeight, rightHeight) + 1;}
}

总结

暂无

Leetcode 257. 二叉树的所有路径

题目：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 {public List<String> binaryTreePaths(TreeNode root) {List<String> res = new ArrayList<String>();if (root == null)return res;List<Integer> paths = new ArrayList<Integer>();traversal(root, res, paths);return res;}private void traversal(TreeNode node, List<String> res, List<Integer> paths){paths.add(node.val);if (node.left == null && node.right == null){StringBuilder sb = new StringBuilder();sb.append(paths.get(0));for (int i = 1; i < paths.size(); i++)sb.append("->" + paths.get(i));res.add(sb.toString());return;}if (node.left != null){traversal(node.left, res, paths);paths.remove(paths.size()-1);}if (node.right != null){traversal(node.right, res, paths);paths.remove(paths.size()-1);}}
}//不用公共paths版的回溯
class Solution {public List<String> binaryTreePaths(TreeNode root) {List<String> res = new ArrayList<String>();traversal(root, res, "");return res;}private void traversal(TreeNode node, List<String> res, String paths){if (node == null)return;if (node.left == null && node.right == null){res.add(new StringBuilder(paths).append(node.val).toString());return;}String tmp = new StringBuilder(paths).append(node.val).append("->").toString();if (node.left != null)traversal(node.left, res, tmp);if (node.right != null)traversal(node.right, res, tmp);}
}

总结

回溯大法好

Leetcode 404.左叶子之和

题目：404.左叶子之和
解析：代码随想录解析

解题思路

代码

/*** 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) {if (root == null)return 0;int leftSum = sumOfLeftLeaves(root.left);int rightSum = sumOfLeftLeaves(root.right);if (root.left != null && root.left.left == null && root.left.right == null)leftSum = root.left.val;return leftSum + rightSum;}
}//迭代就是普通的遍历
class Solution {public int sumOfLeftLeaves(TreeNode root) {if (root == null)return 0;int res = 0;Stack<TreeNode> stack = new Stack<TreeNode>();stack.push(root);while (!stack.isEmpty()){TreeNode node = stack.pop();if (node.left != null && node.left.left == null && node.left.right == null)res += node.left.val;if (node.left != null)  stack.push(node.left);if (node.right != null) stack.push(node.right);}return res;}
}

总结

二叉树递归还得多学学多思考