刷题计划 day15 二叉树（四）【完全二叉树的节点个数】【平衡二叉树】【二叉树的所有路径】
⚡刷题计划day15 二叉树（四）继续，可以点个免费的赞哦~
目录
题目一：222. 完全二叉树的节点个数
法一：普通递归
法二：迭代法
法三：完全二叉树解法
题目二：110. 平衡二叉树
题目三：257. 二叉树的所有路径
法一：递归
1.递归函数参数以及返回值
2.确定递归终止条件
3.确定单层递归逻辑
法二：迭代法
题目一：222. 完全二叉树的节点个数
-
完全二叉树的节点个数
(https://leetcode.cn/problems/count-complete-tree-nodes/description/)
在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2^(h-1) 个节点。
如图：
法一：普通递归
class Solution {public int countNodes(TreeNode root) {if (root==null) return 0;//中间节点+左+右return 1+countNodes(root.left)+countNodes(root.right);}
}法二：迭代法
class Solution {// 迭代法public int countNodes(TreeNode root) {if (root == null) return 0;Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);int result = 0;while (!queue.isEmpty()) {int size = queue.size();while (size -- > 0) {TreeNode cur = queue.poll();result++;if (cur.left != null) queue.offer(cur.left);if (cur.right != null) queue.offer(cur.right);}}return result;}
}法三：完全二叉树解法
完全二叉树只有两种情况，情况一：就是满二叉树，情况二：最后一层叶子节点没有满。
对于情况一，可以直接用 2^树深度 - 1 来计算，注意这里根节点深度为1。
对于情况二，分别递归左孩子，和右孩子，递归到某一深度一定会有左孩子或者右孩子为满二叉树，然后依然可以按照情况1来计算。
AC代码及注释如下：
class Solution {/*** 针对完全二叉树的解法** 满二叉树的结点数为：2^depth - 1*/public int countNodes(TreeNode root) {if (root == null) return 0;TreeNode left = root.left;TreeNode right = root.right;int leftDepth = 0, rightDepth = 0; // 这里初始为0是有目的的，为了下面求指数方便while (left != null) { // 求左子树深度left = left.left;leftDepth++;}while (right != null) { // 求右子树深度right = right.right;rightDepth++;}if (leftDepth == rightDepth) {return (2 << leftDepth) - 1; // 注意(2<<1) 相当于2^2，所以leftDepth初始为0}return countNodes(root.left) + countNodes(root.right) + 1;}
}题目二：110. 平衡二叉树
-
平衡二叉树
(https://leetcode.cn/problems/balanced-binary-tree/description/)
平衡二叉树定义：一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。
详见代码：
class Solution {public boolean isBalanced(TreeNode root) {return getHeight(root) != -1;}
private 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;}// 左右子树高度差大于1，return -1表示已经不是平衡树了if (Math.abs(leftHeight - rightHeight) > 1) {return -1;}return Math.max(leftHeight, rightHeight) + 1;}
}题目三：257. 二叉树的所有路径
-
二叉树的所有路径
(https://leetcode.cn/problems/binary-tree-paths/description/)
说明: 叶子节点是指没有子节点的节点。
题目需要求所有从根节点到叶子节点的路径，那么需要使用前序遍历。
然后每次当遍历到根结点时需要回溯，这也是我们刷题计划第一次设计到回溯，我们要把路径记录下来，需要回溯来回退一个路径再进入另一个路径。
可结合如图理解：
法一：递归
记得我们之前讲的递归三部曲：
1.递归函数参数以及返回值
要传入根节点，记录每一条路径的path，和存放结果集的result，这里递归不需要返回值，代码如下：
void dfs(TreeNode root, List<Integer> paths,List<String> res)2.确定递归终止条件
一般递归我们习惯这样写：
if (cur == NULL) {终止处理逻辑
}但我们这题找到叶子结点就需要结束的处理逻辑了，
那么什么时候算是找到了叶子节点？ 是当 cur不为空，其左右孩子都为空的时候，就找到叶子节点。
所以此题终止条件是：
if (root.left==null && root.right==null){终止处理逻辑
}3.确定单层递归逻辑
因为是前序遍历，需要先处理中间节点，中间节点就是我们要记录路径上的节点，先放进path中。即
paths.add(root.val);然后进行递归回溯，
注意递归与回溯是一一对应的。
if(root.left!=null){dfs(root.left,paths,res);paths.remove(paths.size()-1);
}
if(root.right!=null){dfs(root.right,paths,res);paths.remove(paths.size()-1);
}整体AC代码如下：
class Solution {public List<String> binaryTreePaths(TreeNode root) {List<String> res = new ArrayList<>();List<Integer> paths = new ArrayList<>();dfs(root,paths,res);return res;}public void dfs(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){dfs(root.left,paths,res);paths.remove(paths.size()-1);}if(root.right!=null){dfs(root.right,paths,res);paths.remove(paths.size()-1);}}
}法二：迭代法
注释及代码如下：
public List<String> binaryTreePaths(TreeNode root) {List<String> res = new ArrayList<>();if (root == null)return res;//栈中节点和路径都是成对出现的，路径表示的是从根节点到当前//节点的路径，如果到达根节点，说明找到了一条完整的路径Stack<Object> stack = new Stack<>();//成员变量为object的栈//当前节点和路径同时入栈stack.push(root);stack.push(root.val + "");while (!stack.isEmpty()) {//节点和路径同时出栈String path = (String) stack.pop();TreeNode node = (TreeNode) stack.pop();//如果是根节点，说明找到了一条完整路径，把它加入到集合中if (node.left == null && node.right == null) {res.add(path);}//右子节点不为空就把右子节点和路径压栈if (node.right != null) {stack.push(node.right);stack.push(path + "->" + node.right.val);}//左子节点不为空就把左子节点和路径压栈if (node.left != null) {stack.push(node.left);stack.push(path + "->" + node.left.val);}}return res;
}
参考：力扣题解赞赞~