代码随想录算法训练营第十五天 | 110-平衡二叉树、257-二叉树的所有路径、左叶子之和、完全二叉树的节点个数
LeetCode110 平衡二叉树
题目链接：https://leetcode.cn/problems/balanced-binary-tree/description/
文章讲解：https://programmercarl.com/0110.平衡二叉树.html
视频讲解：https://www.bilibili.com/video/BV1Ug411S7my/?vd_source=b989f2b109eb3b17e8178154a7de7a51
采用后序遍历，左右根，从叶子节点往上求高度
确定终止条件：当遇到空节点，向上返回0
求左子树高度，若为-1则向上返回-1；求右子树高度，若为-1则向上返回-1
中节点处理逻辑：若左右子树高度绝对值小于等于1，则向上返回1 + Math.max(rightHeight, leftHeight)；若大于一，则说明左右子树不平衡，返回-1
class Solution {public boolean isBalanced(TreeNode root) {if(getHeight(root) == -1){return false;}return true;}public int getHeight(TreeNode node){if(node == null){return 0;}int leftHeight = getHeight(node.left);if(leftHeight == -1){return -1;}int rightHeight = getHeight(node.right);if(rightHeight == -1){return -1;}int result = 0;if(Math.abs(rightHeight - leftHeight) > 1){result = -1;}else{result = 1 + Math.max(rightHeight, leftHeight);}return result;}}
LeetCode257 二叉树的所有路径
题目链接：https://leetcode.cn/problems/binary-tree-paths/description/
文章讲解：https://programmercarl.com/0257.二叉树的所有路径.html
视频讲解：https://www.bilibili.com/video/BV1ZG411G7Dh/?vd_source=b989f2b109eb3b17e8178154a7de7a51
这道题要求从根节点到叶子节点的路径，所以需要前序遍历（根左右），方便让父节点指向子节点找对应路径
这题找到叶子节点就要开始结束的处理，所以终止条件不是curNode==null，而是要判断curNode是否为叶子节点，即左右子树是否为空
记录完一条路径，还需要进行回溯，以便回退一个路径再进入另一个路径
class Solution {public List<String> binaryTreePaths(TreeNode root) {List<String> result = new ArrayList<>();List<Integer> path = new ArrayList<>();getPath(root, path, result);return result;}public void getPath(TreeNode node, List<Integer> path, List<String>result){path.add(node.val);if(node.left == null && node.right == null){StringBuilder sb = new StringBuilder();for(int i = 0;i < path.size()-1;i++){sb.append(path.get(i));sb.append("->");}sb.append(path.get(path.size()-1));result.add(sb.toString());return;}if(node.left != null){getPath(node.left, path, result);path.remove(path.size()-1);}if(node.right != null){getPath(node.right, path, result);path.remove(path.size()-1);}}
}
LeetCode404 左叶子之和
题目链接：https://leetcode.cn/problems/sum-of-left-leaves/description/
文章讲解：https://programmercarl.com/0404.左叶子之和.html
视频讲解：
题目要求的是左叶子，但不能从叶子节点本身直接判断其是否为左叶子，所以要从左叶子的父节点开始判断
遍历到空节点，那么左叶子值肯定为0
遍历到叶子节点，由于无法判断其是否为左叶子，所以也返回0
当遇到左叶子节点的时候（从其父节点判断），记录数值，然后通过递归求取左子树左叶子之和，和右子树左叶子之和，相加便是整个树的左叶子之和
class Solution {public int sumOfLeftLeaves(TreeNode root) {if(root == null){return 0;}if(root.left == null && root.right == null){return 0;}int value = 0;if(root.left != null && root.left.left == null && root.left.right == null){value = root.left.val;}return value + sumOfLeftLeaves(root.left) + sumOfLeftLeaves(root.right);}
}
LeetCode222 完全二叉树的节点个数
题目链接：https://leetcode.cn/problems/count-complete-tree-nodes/description/
文章讲解：https://programmercarl.com/0222.完全二叉树的节点个数.html
视频讲解：https://www.bilibili.com/video/BV1eW4y1B7pD/?vd_source=b989f2b109eb3b17e8178154a7de7a51
最先想到的是迭代法，采用层序遍历统计节点个数
class Solution {public int countNodes(TreeNode root) {if(root == null){return 0;}int cnt = 0;Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);cnt++;while(!queue.isEmpty()){int size = queue.size();while(size > 0){TreeNode curNode = queue.poll();size--;if(curNode.left != null){queue.offer(curNode.left);cnt++;}if(curNode.right != null){queue.offer(curNode.right);cnt++;}}}return cnt;}
}
后面想到了递归法，当遇到空节点返回0，然后采用后序遍历（左右根），分别递归求左右子树的节点数量，最后返回 1 + leftNum + rightNum
class Solution {public int countNodes(TreeNode root) {if(root == null){return 0;}int leftNum = countNodes(root.left);int rightNum = countNodes(root.right);return 1 + leftNum + rightNum;}
}