Leetcode上有几道关于二叉树的题，都可以用递归的方式解决
递归的三部曲，首先明确递归的终止条件，然后确定递归要解决的问题，返回值，最后依据最小的问题单元进行递归
100 判断两棵二叉树是否相同
public boolean isSameTree(TreeNode p
, TreeNode q
) {
if(p
== null
&& q
== null
)
return true;
if(p
!= null
&& q
!= null
)
return p
.val
== q
.val
&& isSameTree(p
.left
, q
.left
) && isSameTree(p
.right
, q
.right
);
else
return false;
}
104 二叉树的最大深度
public int maxDepth(TreeNode root
) {
if(root
== null
)
return 0;
int leftMaxDepth
= maxDepth(root
.left
);
int rightMaxDepth
= maxDepth(root
.right
);
return Math
.max(leftMaxDepth
, rightMaxDepth
) + 1;
}
111 二叉树的最小深度
public int minDepth(TreeNode root
) {
if(root
== null
)
return 0;
if(root
.left
== null
&& root
.right
!= null
)
return minDepth(root
.right
) + 1;
if(root
.right
== null
&& root
.left
!= null
)
return minDepth(root
.left
) + 1;
int leftMinDepth
= minDepth(root
.left
);
int rightMinDepth
= minDepth(root
.right
);
return Math
.min(leftMinDepth
, rightMinDepth
) + 1;
}
226 反转二叉树
public TreeNode
invertTree(TreeNode root
) {
if(root
== null
)
return null
;
TreeNode left
= invertTree(root
.left
);
TreeNode right
= invertTree(root
.right
);
root
.left
= right
;
root
.right
= left
;
return root
;
}
110 平衡二叉树
public boolean isBalanced(TreeNode root
) {
if(root
== null
)
return true;
int leftDepth
= maxDepth(root
.left
);
int rightDepth
= maxDepth(root
.right
);
if(Math
.abs(leftDepth
- rightDepth
) > 1)
return false;
return (isBalanced(root
.left
) && isBalanced(root
.right
));
}
public int maxDepth(TreeNode root
) {
if(root
== null
)
return 0;
int leftMaxDepth
= maxDepth(root
.left
);
int rightMaxDepth
= maxDepth(root
.right
);
return Math
.max(leftMaxDepth
, rightMaxDepth
) + 1;
}
