给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。
示例： 1 / 2 3 / 4 5返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。
也许我们会认为将根节点的左右子树的高度再加1就能得出答案了，但是注意题目的最后一句：这条路径可能穿过也可能不穿过根结点 ，让我们看看下图的例子：
代码实现：
public class Num543 {
//存储当前二叉树的最长路径
public int max = 0;
public int diameterOfBinaryTree(TreeNode root) {
if(root == null || (root.left == null && root.right == null)){
//空树或者只有根节点，不存在边
return 0;
}
height(root);
return max;
}
//计算高度
private int height(TreeNode root){
if(root == null){
return 0;
}
int l = height(root.left);
int r = height(root.right);
max = Math.max(max,(l + r));
//返回值是求树的深度
return 1 + Math.max(l,r);
}
}
你需要采用前序遍历的方式，将一个二叉树转换成一个由括号和整数组成的字符串。
空节点则用一对空括号 "()" 表示。而且你需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。
示例：
1
/
2 3
/
4输出: "1(2(4))(3)"
解释: 原本将是“1(2(4)())(3())”，
在你省略所有不必要的空括号对之后，
它将是“1(2(4))(3)”
代码实现：
public class Num606 {
StringBuffer sb = new StringBuffer();
public String tree2str(TreeNode root) {
if(root == null){
return " ";
}
//先访问根节点
sb.append(root.val);
//再去处理左子树
if (root.left != null){
//递归的拼接左子树
sb.append("(");
tree2str(root.left);
sb.append(")");
}else {
//此时左树为空，判断右树是否也为空
//只有左空右不空才添加括号
if(root.right != null){
sb.append("()");
}
}
//再去处理右子树
if(root.right != null){
sb.append("(");
tree2str(root.right);
sb.append(")");
}
return sb.toString();
}
}
}编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。 例如如下的先序遍历字符串： ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。
示例：
输入：abc##de#g##f###
输出：c b e g d f a
代码实现：
import java.util.Scanner;
//根据前序遍历结果构建二叉树
public class KY11_BuildTree {
//index表示当前遍历处理到的字符
private static int index = 0;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
//多组输入
while (scanner.hasNext()){
//每次读取一行前序遍历的结果
String str = scanner.next();
//根据前序遍历的字符串构建二叉树
TreeNode root = preOrderBuild(str);
//对其使用中序遍历，输出节点值
inOrder(root);
//每次输出独占一行
System.out.println();
//再下一次输入时，索引index要置为0
index = 0;
}
}
//中序遍历
private static void inOrder(TreeNode root) {
if(root == null){
return;
}
inOrder(root.left);
System.out.print(root.val + " ");
inOrder(root.right);
}
//根据前序遍历的字符串来构建二叉树
private static TreeNode preOrderBuild(String str) {
char cur = str.charAt(index);
if(cur == '#'){
//空节点，不构建节点
return null;
}
TreeNode root = new TreeNode(cur);
index ++;
//递归处理左子树
root.left = preOrderBuild(str);
index ++;
//递归处理右子树
root.right = preOrderBuild(str);
return root;
}
private class TreeNode {
char val;
TreeNode left;
TreeNode right;
TreeNode() {
}
TreeNode(char val) {
this.val = val;
}
TreeNode(char val,TreeNode left,TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
}
此处我们一定要理解递归的过程，多画图理解，下图简单的展示了递归的过程
前序遍历：根左右，结果集的第一个值就是当前树的根节点
中序遍历：左根右，结果集中，左树都在根的左侧，右树都在根的右侧
根据两种遍历的特点，我们可以通过以下三步解题：
代码实现：
public class Num105_buildTree {
int index = 0;
public TreeNode buildTree(int[] preorder, int[] inorder) {
return builldTreeHelper(preorder,inorder,0,preorder.length);
}
//在preorder的[left..right]区间上借助中序遍历，返回二叉树的根节点
private TreeNode builldTreeHelper(int[] preorder, int[] inorder,int left,int right){
if(left > right){
//空区间
return null;
}
if(index == preorder.length){
//已经全部处理完毕
return null;
}
//构建根节点
TreeNode root = new TreeNode(preorder[index]);
index ++;
//找到该节点在中序遍历的位置
int pos = find(root.val,inorder);
root.left = builldTreeHelper(preorder,inorder,left,pos-1);
root.right = builldTreeHelper(preorder,inorder,pos+1,right);
return root;
}
//找到val在inorder里的位置
private int find(int val, int[] inorder) {
for (int i = 0; i < inorder.length; i++) {
if(inorder[i] == val){
return i;
}
}
return -1;
}
}
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）
示例：
我们可以发现规律：设最近公共祖先为 r ,从 r 出发遍历一定能找到节点 p 和 q ，且 p 和 q 一定不在同一颗子树。
代码实现：
public class Num236 {
private TreeNode lca;
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
//找到p和q的所有祖先
findNode(root,p,q);
return lca;
}
//寻找以root为根节点的二叉树是否含有 p 和 q
private boolean findNode(TreeNode root, TreeNode p, TreeNode q) {
if(root == null){
return false;
}
//现在左子树中寻找，找到一个就返回1
int left = findNode(root.left,p,q) ? 1 : 0;
//再再右子树中寻找
int right = findNode(root.right,p,q) ? 1 : 0;
//最后看根节点是否是p或q
int mid = (root == p || root == q) ? 1 : 0;
if(left + mid + right == 2){
//说明root就是我们要找的最近公共祖先
lca = root;
}
//left + mid + right的结果只可能是0或1或2
//0表示root这棵树没有p、q
//1表示在root中找到了一个，只可能出现在一个位置
//2表示在root中两个节点都找到了，且p、q不在同一颗子树中 -> 这就是我们找到lca
return (left + mid + right) > 0;
}
}
要知道，findNode方法不是在找公共祖先，是判断当前树是否是p或者q的祖先,找到一个就说明至少是一个节点的祖先。
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表
二分搜索树（BST）的每个节点的值都满足左子树 < 根 < 右子树 ，它满足以下两个特点：
要求：空间复杂度O(1)（即在原树上操作），时间复杂度 O(n)
如图是二叉树类和链表类，可以发现，二叉树的左子树就对应链表的前驱节点，右子树就对应着后继节点，另外，要得到一个排序的链表，我们就对BST进行中序遍历。
代码实现：
public class JZ36 {
public TreeNode Convert(TreeNode pRootOfTree) {
if(pRootOfTree == null){
return null;
}
//中序遍历
TreeNode leftHead = Convert(pRootOfTree.left);
//遍历之后的尾节点和根节点连接
TreeNode leftTail = leftHead;
while (leftHead != null && leftTail.right != null){
leftTail = leftTail.right;
}
//此时leftTail就是左链表的尾节点
//和根节点拼接
if(leftTail != null){
pRootOfTree.left = leftTail;
leftTail.right = pRootOfTree;
}
//再递归处理右子树
TreeNode rightHead = Convert(pRootOfTree.right);
//再和根节点拼接
if(rightHead != null){
pRootOfTree.right = rightHead;
rightHead.left = pRootOfTree;
}
//返回整个链表的头节点
//左子树为空，就返回根节点，不为空就返回左侧头节点
return leftHead == null ? pRootOfTree : leftHead;
}
}
到此，关于二叉树的学习就告一段落了，可以发现在二叉树的解题中我们经常用到递归，使用时一定要理解递归方法的语义，而不是去纠结递归方法是如何实现的。同时，二叉树方面的题需要我们反复的去练习，加油！
因篇幅问题不能全部显示，请点此查看更多更全内容