网站建设投标书怎么制作,wordpress接入qq登陆,山东营销网站建设设计,重庆网站设计案例链接力扣110-平衡二叉树
思路 1、左右子树高度差不超过1
2、左子树、右子树均为平衡二叉树
3、需要获得树高#xff0c;如果不是平衡的就返回-1#xff1b;如果是平衡#xff0c;就返回对应的高
class Solution {public boolean isBalanced(TreeNode root) {return getH…链接力扣110-平衡二叉树
思路 1、左右子树高度差不超过1
2、左子树、右子树均为平衡二叉树
3、需要获得树高如果不是平衡的就返回-1如果是平衡就返回对应的高
class Solution {public boolean isBalanced(TreeNode root) {return getHeight(root) -1 ? false:true;}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;return Math.abs(leftHeight - rightHeight) 1 ? -1:1 Math.max(leftHeight,rightHeight);}
}链接力扣257- 二叉树的所有路径
思路 1、首先需要将这条路径上的值收集到集合里
2、将集合里的值取出来加上 - 串成String这里需要注意最后一个结节的处理与前面不同需要单独处理只加值即可这里需要用到StringBuilder
3、将遍历好的路径加到res集合中此时需要回溯将最后一个结点值删除再去遍历得到下一条路径
前、中、后遍历
class Solution {public ListString binaryTreePaths(TreeNode root) {ListString res new ArrayList();if (root null) {return res;}ListInteger path new ArrayList();traversal(root, path, res);return res;}// 记录每一条路径的path值之后再转为字符串、存放结果的respublic void traversal(TreeNode root,ListInteger path,ListString res){// 1、逻辑是前序遍历需要先处理中间节点path.add(root.val);// 2、处理左右孩子节点// 左右结点都为空就到了叶子节点位置if(root.left null root.right null){// 因为结果数组里的每个元素是字符串StringBuilder tmp new StringBuilder();// 最后一个值的处理逻辑跟前面不同不需要 -for(int i 0; i path.size() - 1; i){tmp.append(path.get(i)).append(-);}// 单独处理最后一个结点值tmp.append(path.get(path.size()-1));res.add(tmp.toString());// 到这里结束这一次的traversalreturn;}if(root.left ! null){// traversal一次会得到一条路径但是想要得到下一条路径需要回溯到上一节点// 这时需要将path集合中的最后一个结节值删除traversal(root.left,path,res);path.remove(path.size() - 1);}if(root.right ! null){traversal(root.right,path,res);path.remove(path.size() -1);}}
}链接力扣404. 左叶子之和
思路 1、如何判断是左叶子 root.left 还不行需要 root.left.left null root.left.right null 此时leftValue 就是 root.left.val
2、如果是左子树右子树下面还有子树则继续递归每次左子树时都需要判断是否是左叶子
class Solution {// 定义全局变量以便后面相加使用int res 0;public int sumOfLeftLeaves(TreeNode root){if(root null) return 0;if(root.left ! null root.left.left null root.left.right null){res root.left.val;}sumOfLeftLeaves(root.left);sumOfLeftLeaves(root.right);return res;}
}
