代码随想录算法训练营| 110.平衡二叉树、 257. 二叉树的所有路径 、404.左叶子之和、 222.完全二叉树的节点个数

110.平衡二叉树

题目

参考文章

思路：这道题其实求的就是高度，所以我们用类似后序遍历的方法进行。首先查看左右子树的高度，如果左右子树的高度为-1 （这个-1是用于表示高度差大于1的情况），则返回-1

如果左右子树高度不为-1，则判断leftHeight和rightHeight的高度差是否大于1，如果大于1，则返回-1；否则就返回leftHeight和rightHeight的最大值+1；这样就可以找到高度差了，只要不等于-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;}
}

257. 二叉树的所有路径

题目

参考文章

思路：这里用到了前序遍历和回溯算法，设定一个存储路径的数组res和一个存储遍历二叉树中存储二叉树数值的数组paths。然后先把当前元素值添加到paths中，判断当前节点左右子树是否为空，为空，则表示遇到了叶子节点，则把当前的paths数组中的所有的元素放到res中，存储成为一个路径，如果没有遇到叶子节点，则继续遍历，若左节点不为空，则继续遍历左节点，遍历完成就回溯到上一个节点（在paths中），若右节点不为空，则遍历右节点，遍历完成就回溯到上一个节点（在paths中）

代码：

class Solution {public List<String> binaryTreePaths(TreeNode root) {List<String> res = new ArrayList<>();// 存最终的结果if (root == null) {return res;}List<Integer> paths = new ArrayList<>();// 作为结果中的路径traversal(root, paths, res);return res;}private void traversal(TreeNode root, List<Integer> paths, List<String> res) {paths.add(root.val);// 前序遍历，中// 遇到叶子结点if (root.left == null && root.right == null) {StringBuilder sb = new StringBuilder();for (int i = 0; i < paths.size() - 1; i++) {sb.append(paths.get(i)).append("->");}sb.append(paths.get(paths.size() - 1));// 记录最后一个节点res.add(sb.toString());// 收集一个路径return;}// 递归和回溯是同时进行的if (root.left != null) { // 左traversal(root.left, paths, res);paths.remove(paths.size() - 1);// 回溯}if (root.right != null) { // 右traversal(root.right, paths, res);paths.remove(paths.size() - 1);// 回溯}}
}

404.左叶子之和 

题目

参考文章

思路：这题求左叶子的和，用后序遍历的方式最合适，因为就是相当于找到了当前节点左右子树对应的左叶子节点值的和，然后返回给当前节点，再一层层往父节点返回。所以先寻找左右子树的左叶子节点值的和，然后当找到当前节点的左子树不为空，且左子树左右子树都为空，表示当前节点的左子树就是左叶子节点，记录该值即可；最后返回他们的和即可。sum其实就是相当于返回给父节点的左右子树的左叶子节点值的和。

代码：

class Solution {public int sumOfLeftLeaves(TreeNode root) {if (root == null) return 0;//左遍历int leftValue = sumOfLeftLeaves(root.left);    //右遍历int rightValue = sumOfLeftLeaves(root.right);  //找对应左叶子的值，即遍历到左叶子节点的父节点时，进行操作                                      int midValue = 0;if (root.left != null && root.left.left == null && root.left.right == null) { midValue = root.left.val;}//最后返回他们的和int sum = midValue + leftValue + rightValue;  // 中return sum;}
}

 222.完全二叉树的节点个数

题目

参考文章

思路：题目中的是完全二叉树，所以我们可以用完全二叉树的特性，在某种情况下，其子树有可能出现满二叉树的情况，所以我们当遇到要给满二叉树时，我们可以直接用满二叉树的公式来返回节点数即可（2^满二叉树高度-1），其他情况则遍历左右子树，统计个数即可。

代码：

class Solution {public int countNodes(TreeNode root) {if(root==null){return 0;}TreeNode left = root.left;TreeNode right = root.right;int leftDepth=0;int rightDepth=0;//左子树深度while(left!=null){left=left.left;leftDepth++;}//右子树深度while(right!=null){right=right.right;rightDepth++;}if(leftDepth==rightDepth){return (2 << leftDepth) - 1; //利用满二叉树的特点，返回节点个数}return countNodes(root.left)+countNodes(root.right)+1;}
}