算法日记 13 day 二叉树
今天继续二叉树啊！！！
题目：平衡二叉树
110. 平衡二叉树 - 力扣（LeetCode）
给定一个二叉树，判断它是否是 平衡二叉树
题目分析：
平衡二叉树指的是一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。
在之前的题中，我们做过了求树的最大深度，不过我们使用的是求高度的写法，通过后序遍历的方式将子节点的高度返回给父节点。同样的，平衡二叉树的判断也是这种方式。
public class Solution {public bool IsBalanced(TreeNode root) {return (GetHeight(root)==-1)?false:true;}public int GetHeight(TreeNode root){if(root==null) return 0;int left=GetHeight(root.left);//使用后序遍历，这样能够将子节点的信息返回给父节点if(left==-1) return-1;int right=GetHeight(root.right);if(right==-1) return-1;int res;if(Math.Abs(left-right)>1)//左右子树的高度差{res=-1;}else{res=1+Math.Max(left,right);}return res;}
}题目：二叉树的所有路径
257. 二叉树的所有路径 - 力扣（LeetCode）
给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。
叶子节点 是指没有子节点的节点。
示例 1：
输入：root = [1,2,3,null,5] 输出：["1->2->5","1->3"]
题目分析：
这道题目要求从根节点到叶子的路径，所以需要前序遍历，这样才方便让父节点指向孩子节点，找到对应的路径。
在这道题目中将第一次涉及到回溯，因为我们要把路径记录下来，需要回溯来回退一个路径再进入另一个路径。记住回溯是需要回退的。
回溯的本质其实就是递归，所以写法上和递归差不多。
public class Solution {public IList<string> BinaryTreePaths(TreeNode root) {List<int> path=new List<int>();List<string> res=new List<string>();if (root == null) return res;BrackTracing(root,path,res);return res;}public void BrackTracing(TreeNode root,List<int> path,List<string> res){path.Add(root.val);//记录当前的节点if(root.right==null&&root.left==null)//叶子节点{string str="";for(int i=0;i<path.Count-1;i++){str+=path[i].ToString();str+="->";}str+=path[path.Count-1].ToString();res.Add(str);}if(root.left!=null){BrackTracing(root.left,path,res);path.RemoveAt(path.Count-1);//回退一个节点}if(root.right!=null){BrackTracing(root.right,path,res);path.RemoveAt(path.Count-1);}}
}题目：左叶子之和
404. 左叶子之和 - 力扣（LeetCode）
给定二叉树的根节点 root ，返回所有左叶子之和。
示例 1：
输入: root = [3,9,20,null,null,15,7] 输出: 24 解释: 在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24
题目分析：
这个左叶子是指节点A的左孩子不为空，且左孩子的左右孩子都为空（说明是叶子节点），那么A节点的左孩子为左叶子节点。所有我们应该是通过父节点去判断左子节点是否为左叶子节点
public class Solution {public int SumOfLeftLeaves(TreeNode root) {if(root==null) return 0;int left=SumOfLeftLeaves(root.left);if (root.left!=null && root.left.left==null && root.left.right==null){// 左子树就是一个左叶子的情况left+=root.left.val;}int right=SumOfLeftLeaves(root.right);int sum=left+right;return sum;}
}题目：完全二叉树的节点个数
222. 完全二叉树的节点个数 - 力扣（LeetCode）
给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。
完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。
题目分析：
题目提供的是完全二叉树。那么对于完全二叉树而言。
完全二叉树只有两种情况，情况一：就是满二叉树，情况二：最后一层叶子节点没有满。
对于情况一，可以直接用 2^树深度 - 1 来计算，注意这里根节点深度为1。
对于情况二，分别递归左孩子，和右孩子，递归到某一深度一定会有左孩子或者右孩子为满二叉树，然后依然可以按照情况1来计算。
public 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(rightDepth==leftDepth)//左右深度相同，是一个满二叉树{return (int)Math.Pow(2,leftDepth+1)-1;}return CountNodes(root.left)+CountNodes(root.right)+1;}
}
对于更详细的解析与其他语言的代码块，可以去代码随想录上查看。
代码随想录 (programmercarl.com)