草稿圖網(wǎng)站
java的Deque

Leetcode 110.平衡二叉樹

題目：** 110.平衡二叉樹**
解析：代碼隨想錄解析

解題思路

求高度的方法加一點(diǎn)判斷

代碼

/*** 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;*     }* }*///使用求高度來(lái)代替，使用-1來(lái)減枝
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;}
}

總結(jié)

暫無(wú)

Leetcode 257. 二叉樹的所有路徑

題目：257. 二叉樹的所有路徑
解析：代碼隨想錄解析

解題思路

使用回溯法的思想，終止條件（葉子節(jié)點(diǎn)），遍歷（遞歸前加入元素，遞歸結(jié)束刪除元素）

代碼

/*** 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);}
}

總結(jié)

回溯大法好

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;}
}

總結(jié)

二叉樹遞歸還得多學(xué)學(xué)多思考