javaday14_0">java算法day14
- 222 完全二叉树的节点个数。
- 110 平衡二叉树
- 257 二叉树的所有路径
222 完成二叉树的节点个数
解法1，层序遍历，迭代解法。
就是层序遍历的模板题。
java">/*** 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 countNodes(TreeNode root) {Deque<TreeNode> que = new ArrayDeque<>();if(root==null){return 0;}que.offerLast(root);int count = 0;while(!que.isEmpty()){int size = que.size();count +=size;while(size>0){TreeNode temp = que.pollFirst();if(temp.left!=null){que.offerLast(temp.left);}if(temp.right!=null){que.offerLast(temp.right);}size--;}}return count;}
}
解法二：递归解法。
首先还是不要扣细节，从大体上观察，然后才是拆分子问题求解。
大体上就是计算root的左右子树的节点个数总和相加，然后算上root就是+1。
如果是为null了，那说明下面没有了，直接return 0。所以递归出口也找到了。
java">class Solution {public int countNodes(TreeNode root) {if(root==null){return 0;}//返回左右子树的节点总和，然后加上本层的节点。return 1+countNodes(root.left)+countNodes(root.right);}
}
110 平衡二叉树
解法1：
还是递归思想。
粗略的来想。
递归的过程中，每一层需要做的事就是计算左右子树的最大高度的绝对值相减是否大于。然后递归检查左右子树。根据这个思想可以得到。
这题我写的时候没注意到一个问题，一定要紧扣题目问什么，这题我就忘写了与题目相关的进入下一层的逻辑。
java">class Solution {public boolean isBalanced(TreeNode root) {//能走到这说明到底了，那就是这个过程都是满足条件，所以为trueif(root==null){return true;}//每层要干的事if(Math.abs(maxDepth(root.left)-maxDepth(root.right))>1){return false;}//进入下一层。return isBalanced(root.left) && isBalanced(root.right);}//写一个函数来递归计算左右子树的最大高度int maxDepth(TreeNode root){if(root==null){return 0;}int leftMax = maxDepth(root.left);int rightMax = maxDepth(root.right);return 1+Math.max(leftMax,rightMax);}
}
这个解法有弊端，我这种解法属于自顶向下的，所以有很多的冗余计算，冗余的地方在于，我每次进入下一层，我就要调用一次计算左右子树最大高度，算一次最大高度，那就要往下递归。
所以这就是优化的地方。因此有了解法二
解法二：自底向下解法。
https://leetcode.cn/problems/balanced-binary-tree/solutions/746538/shu-ju-jie-gou-he-suan-fa-ping-heng-er-c-ckkm/
这篇题解是我看过最直观的图解。
思路：
1.这也是做本题得到的一个新思考，怎样才能做到自顶向上？ 回答是利用后序遍历的思想。在后序遍历中，我们先处理左子树，然后右子树，最后才是处理当前节点。这样就做到了得到左右子树的全部信息后才来处理当前节点。而且还是在回溯的过程中进行。
总结：后序遍历提供了自底向上的信息流
2.代码整体思路：
使用一个辅助函数height来同时计算树的高度和检查平衡性。如果树是平衡的，height返回树的实际高度。如果不平衡，返回-1。
主函数要干的就是返回这个辅助函数的返回结果，如果辅助函数返回-1，那么，在底部就有一个位置不满足平衡二叉树的条件。平衡二叉树的判定是，每个节点都要递归的满足平衡二叉树的定义。由于是自底向上返回结果，所以，这个-1的值是可以带上来的，只要做条件判断即可。
3.辅助函数的具体细节
就按上面所说的想法实现，但是用的是后序遍历。由于平衡二叉树的判断本质还是左右子树高度查，因此在每一层还是要计算左右子树的高度查。但他不一样的点就在于，结果直接是从底层开始计算，所以只要底层返回了下面的高度，就可以避免重复的计算。
接下来直接看代码。
java">class Solution {public boolean isBalanced(TreeNode root) {//就是返回辅助函数的结果return height(root)>=0;}//传根节点进来public int height(TreeNode root){//递归出口，到底了，返回值就是0。没有高度if(root==null){return 0;}//后序遍历的思想，先往底部走int leftHeight = height(root.left);int rightHeight = height(root.right);//这里就是到了底层之后，归 的逻辑//之前说了，一旦有一个子树不满足平衡二叉树的定义，那么整体就不满足，所以这个结果要带上去。每一层都做这样的判断，那就能够带到顶部。//返回-1的情况有三种，左子树上有不满足的，或者右子树上有不满足的，或者到当前层才不满足的。if(leftHeight==-1 || rightHeight==-1 || Math.abs(leftHeight-rightHeight)>1){return -1;}else{//能走到这说明左右子树都满足了二叉平衡树，那么加上本层的高度，往上返回。return Math.max(leftHeight,rightHeight)+1;}}
}
从底部，得出底部的信息，归的时候带上底部的信息，可以避免重复计算。从而实现优化。
二叉树路径问题
主要分为两大类。
1.自顶向下：
就是从某一个节点（不一定是根节点），从上到下寻找路径，到某一个节点（不一定是叶节点）结束。
自顶向下解题模板
首先想想自顶向下这个过程，可以清楚的类比为前序遍历的过程。因此理解下面模板的过程中，就当为前序遍历。
不回溯版本
java">class Solution {//用于收集所有路径的结果集List<List<Integer>> res = new ArrayList<>();//主函数，用来启动dfs，最后返回所有路径的结果集public List<List<Integer>> findPaths(TreeNode root) {dfs(root, new ArrayList<>());return res;}private void dfs(TreeNode root, List<Integer> path) {//递归出口。一旦走到了这里，说明走到了叶子节点下面的空节点。所以下面就不用担心path.add收集到空的问题。if (root == null) return;//所以每进到下一层，就先收集节点。 path.add(root.val);//然后判断是否是叶子节点，是的话就把路径加入结果集res。然后return，这条路就已经走完了。if (root.left == null && root.right == null) {//这里也是一个细节，这里是复制一份path，因为如果直接用那份path，在之后的状态会影响到里面的元素，所以这里是复制一份路径，加入结果集。res.add(new ArrayList<>(path));return;}//这里也是递归左右子树，因为你要分开了，两条路的后面的路径肯定是不相同的，所以后面的路径要分别新弄一个副本记录。如果用同一个path，那么就会导致path里面的元素会互相影响。dfs(root.left, new ArrayList<>(path));dfs(root.right, new ArrayList<>(path));}
}
回溯版本
java">class Solution {
//结果集List<List<Integer>> res = new ArrayList<>();//主函数public List<List<Integer>> findPaths(TreeNode root) {dfs(root, new ArrayList<>());return res;}private void dfs(TreeNode root, List<Integer> path) {//递归出口if (root == null) return;path.add(root.val);//检查是否为叶子节点，这里不同于非回溯的点就在于，你在判断为是叶子节点后，也不能直接停下来，而是要进行回溯。即处理完这层的结果集之后，还要把刚刚加进来的元素给删了。这才完成了该叶子节点的任务。//本质还是前序遍历。if (root.left == null && root.right == null) {res.add(new ArrayList<>(path));} else {//递归遍历左右子树。现在可以看到，用的一直都是同一个path了。dfs(root.left, path);dfs(root.right, path);}//回溯//这里回溯的思考很重要//回溯并不是只删除刚加入的叶子节点，而是不管是任意节点，在完成当前节点的探索之后，需要将当前节点从路径中移除。所以上面的dfs下一层之后，回来的时候还是要走remove回溯。//确保我们回到父节点时，路径恢复到进入当前节点的状态。path.remove(path.size() - 1); // 回溯}
}
2.非自顶向下：
就是从任意节点到任意节点的路径，不需要自顶向下。
257 二叉树的所有路径
类别为：自顶向下
所以用回溯的模板做：
java">class Solution {public List<String> binaryTreePaths(TreeNode root) {List<String> result = new ArrayList<>();if (root == null) return result;dfs(root, new StringBuilder(), result);return result;}private void dfs(TreeNode node, StringBuilder path, List<String> result) {if (node == null) return;int len = path.length();if (len > 0) path.append("->");path.append(node.val);if (node.left == null && node.right == null) {result.add(path.toString());} else {dfs(node.left, path, result);dfs(node.right, path, result);}path.setLength(len); // 回溯}
}
不回溯的模板：
java">/*** 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> result = new ArrayList<>();if (root == null) return result;dfs(root, "", result);return result;}private void dfs(TreeNode node, String path, List<String> result) {if (node == null) return;path += node.val;if (node.left == null && node.right == null) {result.add(path);return;}path += "->";dfs(node.left, path, result);dfs(node.right, path, result);}
}
