一、二叉树的翻转
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) {
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 1 - 2^h 1−2h 个节点。
- 代码：
class Solution {
public int countNodes(TreeNode root) {
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){
if(node == null) return 0;
int leftHeight = getHeight(node.left);
int rightHeight = getHeight(node.right);
if(leftHeight==-1 || rightHeight==-1){
return -1;
}
if(Math.abs(leftHeight-rightHeight) > 1){
return -1;
}
return 1+Math.max(leftHeight,rightHeight);
}
public boolean isBalanced(TreeNode root) {
if(getHeight(root)!=-1){
return true;
} else {
return false;
}
}
}
