一、二叉树的翻转

1. 226【翻转二叉树】

• 题目： 给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
• 代码：

class Solution {public TreeNode invertTree(TreeNode root) {//翻转二叉树，实际上就是交换左右结点//使用递归来交换，根左右if(root == null) return null;swapChildren(root);invertTree(root.left);invertTree(root.right);return root;}public void swapChildren(TreeNode root){TreeNode temp = root.right;root.right = root.left;root.left = temp;}
}

二、对称二叉树

1. 101 【对称二叉树】

• 题目： 给你一个二叉树的根节点 root ， 检查它是否轴对称。
• 代码：

class Solution {public boolean isSymmetric(TreeNode root) {//对称二叉树，对称的是根的左右子树//不能完全遍历左右子树之后比较遍历结果，因为不能区分左结点或右结点为空的情况//左子树通过根左右的方式遍历//右子树通过根右左的方式遍历//若左右子树遍历的结果相同，则是对称二叉树TreeNode left = root.left;TreeNode right = root.right;return inorder(left,right);}public boolean inorder(TreeNode left,TreeNode right){if(left==null && right!=null) return false;if(left!=null && right==null) return false;if(left==null && right==null) return true;if(left.val != right.val) return false;//前序遍历boolean f1 = inorder(left.left,right.right);boolean f2 = inorder(left.right,right.left);return f1&&f2;}
}

2. 100【相同的树】

• 题目： 给你两棵二叉树的根节点p和q，编写一个函数来检验这两棵树是否相同。如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
• 代码：

class Solution {public boolean isSameTree(TreeNode p, TreeNode q) {//递归遍历两棵树，比较每个相应结点的值是否相等if(p==null && q!=null) return false;if(p!=null && q==null) return false;if(p==null && q==null) return true;if(p.val != q.val) return false;boolean f1 = isSameTree(p.left,q.left);boolean f2 = isSameTree(p.right,q.right);return f1&&f2;}
}

三、二叉树的深度

1. 104【二叉树的最大深度】

• 题目： 给定一个二叉树 root ，返回其最大深度。二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
• 代码：

class Solution {public int maxDepth(TreeNode root) {//求二叉树的深度本质上是遍历二叉树//上一篇有记录使用层序遍历求二叉树的深度//这里使用后序遍历求二叉树的深度if(root == null) return 0;int leftDepth = maxDepth(root.left);int rightDepth = maxDepth(root.right);return 1+Math.max(leftDepth,rightDepth);}
}

2. 559【n叉树的最大深度】

• 题目： 给定一个 n 叉树，找到其最大深度。最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。
• 代码：

class Solution {public int maxDepth(Node root) {//这里同样用后序遍历来求解if(root == null) return 0;int max = 0;List<Node> childNode = root.children;for(Node n:childNode){max = Math.max(max, maxDepth(n));}return 1+max;}
}

3. 111【二叉树的最小深度】

• 题目： 给定一个二叉树，找出其最小深度。最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
• 代码：

class Solution {public int minDepth(TreeNode root) {//注意最小深度是根到叶子结点的最短距离，//因此不能使用min(leftDepth,rightDepth)，这样求得的不一定是到叶子结点的距离if (root == null) return 0;int leftDepth = minDepth(root.left);int rightDepth = minDepth(root.right);if (root.left != null && root.right == null) {return 1 + leftDepth;}if (root.left == null && root.right != null) {return 1 + rightDepth;} else {return 1 + Math.min(leftDepth, rightDepth);}}
}

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

• 题目： 给你一棵完全二叉树的根节点 root ，求出该树的节点个数。
  完全二叉树的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 $1-2^h$ 个节点。
• 代码：

class Solution {public int countNodes(TreeNode root) {//将完全二叉树划分为多个满二叉树，求每个满二叉树的节点个数//完全二叉树如果最左边的节点个数==最右边节点个数，则是一个满二叉树//满二叉树的节点个数=2^n-1，n是树的深度if(root == null) return 0;int leftNum =0;int rightNum = 0;TreeNode tempNode = root;while(tempNode.left != null){leftNum++;tempNode = tempNode.left;}tempNode = root;while (tempNode.right != null){rightNum++;tempNode = tempNode.right;}if(leftNum == rightNum){return (2<<rightNum)-1;}else{int leftDepth = countNodes(root.left);int rightDepth = countNodes(root.right);return leftDepth+rightDepth+1;}}
}

5. 110【平衡二叉树】

• 题目： 给定一个二叉树，判断它是否是高度平衡的二叉树。
• 代码：

class Solution {public int getHeight(TreeNode node){//该题不可以简单的使用最大深度-最小深度<=1来判断//如果一棵树只有一条路径，则最大深度-最小深度=0<1//但它不一定是平衡的if(node == null) return 0;int leftHeight = getHeight(node.left);int rightHeight = getHeight(node.right);if(leftHeight==-1 || rightHeight==-1){return -1;}//左右子树高度相差1或0都可以if(Math.abs(leftHeight-rightHeight) > 1){return -1;}return 1+Math.max(leftHeight,rightHeight);}public boolean isBalanced(TreeNode root) {//平衡二叉树：每个节点的左右子树高度差的绝对值不超过1//计算左右子树的高度，然后计算高度差的绝对值是否为1if(getHeight(root)!=-1){return true;} else {return false;}}
}