【数据结构 Java 版】二叉树的实现（超多图、超详解）

2年前 (2022) 程序员胖胖胖虎阿

359 0 0

文章目录

1. 树型结构
- 1.1 概念
- 1.2 要掌握的知识点
- 1.3 树的存储形式
- 1.4 树的应用
2. 二叉树
- 2.1 概念
- 2.2 二叉树的基本形态
- 2.3 两种特殊的二叉树
- - 2.3.1 满二叉树
  - 2.3.2 完全二叉树
- 2.4 二叉树的性质
- 2.5 二叉树的存储
- 2.6 二叉树的基本操作
- - 2.6.1 二叉树的前、中、后序遍历（递归实现）
  - 2.6.2 二叉树的层序遍历
  - 2.6.2 二叉树的实现
- 2.7 前中后序的非递归实现
3. 二叉树练习题
- 3.1 二叉树基础练习题
- - 3.1.1 二叉树的前序遍历
  - 3.1.2 二叉树的中序遍历
  - 3.1.3 二叉树的后序遍历
  - 3.1.4 相同的树
  - 3.1.5 另一棵树的子树
  - 3.1.6 二叉树的最大深度
  - 3.1.7 平衡二叉树
  - 3.1.8 对称二叉树
- 3.2 二叉树进阶练习题
- - 3.2.1 二叉树的构建及遍历
  - 3.2.2 二叉树的层序遍历
  - 3.2.3 二叉树的最近公共祖先
  - 3.2.4 二叉搜索树与双向链表
  - 3.2.5 从前序与中序遍历序列构造二叉树
  - 3.2.6 从中序与后序遍历序列构造二叉树
  - 3.2.7 根据二叉树创建字符串

1. 树型结构

1.1 概念

树：是一种非线性的数据结构，它是由 n（n>=0）个有限节点组成的一个具有层次关系的集合。把它叫做树是因为它看起来像一颗倒挂的树，它是根朝上，叶朝下。

【数据结构 Java 版】二叉树的实现（超多图、超详解）

特点：

有一个特殊的节点，称为根节点，根节点没有前驱节点

除根节点外，其余节点被分成 M（M>0）个互不相交的集合（T1、T2、…、Tm），其中每一个集合 Ti（1<=i<=m）又是一颗与树类似的子树。每颗子树的根节点有且只有一个前驱，可以有0个或多个后继

一颗 N 个节点的树有 N-1 条边

树是递归定义的

注意：

子树是不相交的，即除每个节点有且仅有一个父节点。而下面的几种情况都是非树

情况一：

情况二：

情况三：

1.2 要掌握的知识点

大家可以配合此图，食用以下关于树的知识点【数据结构 Java 版】二叉树的实现（超多图、超详解）

节点的度： 一个节点含有的子树的个数称为该节点的度。如上图，T 节点的度为4

树的度： 一颗树中，最大的节点的度称为树的度。如上图，该树的度为4

叶子节点或终端节点： 度为0的节点称为叶子节点。如上图，T4、T11、T21、T22、T31、T32、T33为叶子节点

双亲节点或父节点： 若一个节点含有子节点，则这个节点称为其子节点的父节点。如上图，T 节点是 T4 节点的父节点

孩子节点或子节点： 一个节点含有的子树的根节点称为该节点的子节点。如上图，T4 节点是 T 节点的子节点

根节点： 一颗树中，没有双亲节点的节点称为根节点。如上图，T 节点为根节点

节点的层次： 从根开始定义，根为第1层，根的子节点为第二层，以此类推。如上图，该树有3层

节点的深度： 某节点层次是第几层，则它的深度是多少。如上图，T 节点深度为1，T1 节点深度为2

树的高度： 树中节点的最大层次。如上图，树的高度为3

非终端节点或分支节点： 度不为0的节点。如上图，T、T1、T2、T3 为分支节点

兄弟节点： 父亲节点相同的节点互称为兄弟节点。如上图，T1、T2、T3、T4 互称为兄弟节点

堂兄弟节点： 双亲在同一层次的节点互称为堂兄弟节点。如上图，T11、T21 互称为堂兄弟节点

节点的祖先： 从根节点到该节点所经过分支上的所有节点都称为该节点的祖先。如上图，T、T1 节点都为 T11 节点的祖先

子孙： 以某节点为根的子树中，任意节点都称为该节点的子孙。如上图，该树中除 T 节点其它节点都是 T 节点的子孙

森林： 由 m（m>=0）棵互不相交的树的集合称为森林。

1.3 树的存储形式

树是一种非线性的数据结构，所以存储数据相较于线性结构其实要麻烦很多。常用的方法有：双亲表示法、孩子表示法、孩子兄弟表示法等等。这里我们主要介绍最常用的孩子兄弟表示法。

孩子兄弟表示法的代码表现形式：

class Node{
    int val;			// 树中存储的数据
    Node firstChild;	// 第一个孩子的引用
    Node nextBrother;	// 下一个兄弟的引用
}

我们可以引用下面这棵树的图片，对它进行解析来理解上述代码的意思【数据结构 Java 版】二叉树的实现（超多图、超详解）

解析： 每一个节点都有一个第一个孩子结点和下一个兄弟结点，通过这两个结点，就可以将这棵树的所有结点联系起来。使得我们可以遍历，并将数据存储。

【数据结构 Java 版】二叉树的实现（超多图、超详解）

1.4 树的应用

其实我们电脑的文件系统管理和树的结构很相似，尤其是有着一切皆文件之称的 linux 系统。【数据结构 Java 版】二叉树的实现（超多图、超详解）

因此我们可以使用树的知识，去构建一个系统的目录和文件。

2. 二叉树

2.1 概念

二叉树：是 n 个有限元素的集合，该集合或者为空，或者是由一个根节点加上两棵不相交的，被分别称为左子树和右子树的二叉树组成。

【数据结构 Java 版】二叉树的实现（超多图、超详解）

特点：

当集合为空时，该二叉树称为空二叉树。

在二叉树中，一个元素也称为一个结点。

每个结点最多有两棵子树，即二叉树不存在度大于2的结点。

二叉树的子树有左右之分，其次子树的次序不能颠倒，因此二叉树是有序树。

2.2 二叉树的基本形态

一般二叉树都是由以下四种形态的二叉树组合形成的【数据结构 Java 版】二叉树的实现（超多图、超详解）

注意：

子树也必须是二叉树才能满足该树整体是一个二叉树

2.3 两种特殊的二叉树

2.3.1 满二叉树

满二叉树： 一个二叉树，如果每一层的节点数都达到最大值，则这个二叉树就是满二叉树。

性质： 如果一个二叉树的层数是k，且节点数是 2^k-1，则它就是满二叉树。

【数据结构 Java 版】二叉树的实现（超多图、超详解）

2.3.2 完全二叉树

完全二叉树： 完全二叉树是效率很高的数据结构，它是由满二叉树引申出来的。它的叶子节点只会出现在最后2层，且最后一层的叶子节点都靠左对齐。（满二叉树是一种特殊的完全二叉树）

【数据结构 Java 版】二叉树的实现（超多图、超详解）

2.4 二叉树的性质

若规定根节点的层数为1，则一棵非空二叉树的第 i 层上最多有 2^i-1（i>0）个节点

若规定只有根节点的二叉树的深度为1，则深度为 k 的二叉树的最大节点数是 2^k-1（k>=0）

对任何一棵二叉树，如果其叶子节点个数为 m，度为2的非叶子节点个数为 n，则有 m=n+1

具有 n 个节点的完全二叉树的深度为 log₂(n+1) 向上取整

对于具有 n 个节点的完全二叉树，如果按照从上至下、从左至右的顺序对所有节点从0开始编号，则对序号为 i 的节点有：

若 i>0，双亲序号为：(i-1)/2

若 i=0，i 为根节点编号，无双亲节点

若 2i+1<n，左孩子序号为：2i+1，否则没有左孩子

若 2i+2<n，右孩子序号为：2i+2，否则没有右孩子

练习题：

假设一棵完全二叉树中总共有1000个节点，则该二叉树中有____个叶子节点，____个非叶子节点，____个节点只有左孩子，____个节点只有右孩子。

答案：

500、500、1、0

解析：

由于这是一个完全二叉树，所以不可能出现只有右孩子的节点，故最后一空为0

通过节点个数1000，可以推导出该树的深度为10

第10层节点数可以通过总节点数减去前9层节点数得到，为1000-511=489

叶子节点数=第10层的节点数+第九层度为0的节点数，而通过第10层的节点数可以知道他们的父节点有489/2+1=245

由于这是一个完全二叉树，所以第9层的节点肯定是满的，易得第9层节点数为256，而去除第九层度不为0的节点数，得到第九层叶子节点有256-245=11

故叶子节点数为489+11=500，非叶子节点数为1000-500=500

而完全二叉树的节点只有左子树的结果有1或0，通过第十层的节点数489为偶数，我们知道肯定有一个父节点只有一个孩子节点，即只有左子树的节点为1

2.5 二叉树的存储

二叉树的存储结构分为：顺序存储（在堆中介绍）和类似于链表的链式存储

二叉树的链式存储是通过一个一个的节点引用起来的，表示方法有：孩子表示法和孩子双亲表示法

孩子表示法：

class Node{
    int val;		// 数值域
    Node left;		// 左孩子的引用，常常代表以左孩子为根的整棵树
    Node right;		// 右孩子的引用，常常代表以右孩子为根的整棵树
}

孩子双亲表示法：

class Node{
    int val;		// 数值域
    Node left;		// 左孩子的引用，常常代表以左孩子为根的整棵树
    Node right;		// 右孩子的引用，常常代表以右孩子为根的整棵树
    Node parent;	// 当前节点的根节点
}

2.6 二叉树的基本操作

2.6.1 二叉树的前、中、后序遍历（递归实现）

二叉树是一个非线性的数据结构，对它进行遍历的方式其实有多种，因此如果我们都以自己的方式去遍历二叉树，那么这个代码的易懂性就大大降低，显得很混乱。

为此对于二叉树，根据遍历根节点的先后次序，我们有以下三种遍历方式（N：代表根节点；L：代表根节点的左子树；R：代表根节点的右子树）

前序遍历（NLR）： 先访问根节点➡根的左子树➡根的右子树

中序遍历（LNR）： 先访问根的左子树➡根节点➡根的右子树

后序遍历（LRN）： 先访问根的左子树➡根的右子树➡根节点

练习题：

请写出下面这棵二叉树的四种遍历方式

答案：

前序遍历：ABDEHCFG

中序遍历：DBEHAFCG

后序遍历：DHEBFGCA

注意：

不管是前序、中序还是后序遍历，遍历的路径是一样的，但访问的方式是不一样的

2.6.2 二叉树的层序遍历

除了前中后序遍历外，二叉树还有一种很直观的遍历方式：层序遍历。层序遍历就是从二叉树的根节点出发，首先访问该树的第一层的根节点，然后从左到右访问第二层的节点，接着是第三层的节点，以此类推。

【数据结构 Java 版】二叉树的实现（超多图、超详解）

对于上图的树，使用层序遍历，节点被访问的顺序为：ABCDEFGH

层序遍历一般使用非递归的方式，具体的实现方法可以使用队列。【数据结构 Java 版】二叉树的实现（超多图、超详解）

代码： 实现层序遍历

public void levelOrderTraversal(Node root){
    if(root==null){
        return;
    }
    Queue<Node> queue=new LinkedList<>();
    queue.offer(root);
    while(!queue.isEmpty()){
        Node node=queue.poll();
        System.out.print(node.val+" ");
        if(node.left!=null) {
            queue.offer(node.left);
        }
        if(node.right!=null) {
            queue.offer(node.right);
        }
    }
}

相关习题：

习题一： 求一棵树的左视图

代码：

public List<Character> leftMap(Node root) {
    List<Character> ret=new ArrayList<>();
    if(root==null){
        return ret;
    }
    Queue<Node> queue =new LinkedList<>();
    queue.offer(root);
    while(!queue.isEmpty()){
        int size=queue.size();
        int count=size;
        while(size>0){
            Node top=queue.poll();
            if(count==size){
                ret.add(top.val);
            }
            if(top.left!=null){
                queue.offer(top.left);
            }
            if(top.right!=null){
                queue.offer(top.right);
            }
            size--;
        }
    }
    return ret;
}

习题二： 求二叉树的最大宽度

代码：

public int maxWidth(Node root) {
    if(root==null){
        return 0;
    }
    Queue<Node> queue =new LinkedList<>();
    queue.offer(root);
    int max=0;
    while(!queue.isEmpty()){
        int size=queue.size();
        max=Math.max(max,size);
        while(size>0){
            Node top=queue.poll();
            if(top.left!=null){
                queue.offer(top.left);
            }
            if(top.right!=null){
                queue.offer(top.right);
            }
            size--;
        }
    }
    return max;
}

习题三： 判断一棵树是不是完全二叉树

代码：

public boolean isCompleteTree(Node root){
    if(root==null){
        return true;
    }
    Queue<Node> queue=new LinkedList<>();
    queue.offer(root);
    while(!queue.isEmpty()){
        Node top=queue.poll();
        if(top==null){
            break;
        }
        queue.offer(top.left);
        queue.offer(top.right);
    }
    while(!queue.isEmpty()){
        Node top=queue.peek();
        if(top!=null){
            return false;
        }
        queue.poll();
    }
    return true;
}

2.6.2 二叉树的实现

由于二叉树的创建一般使用递归，而递归创建二叉树将在后面重点介绍。故这里使用穷举法来创建下面这棵二叉树【数据结构 Java 版】二叉树的实现（超多图、超详解）

实现代码：

class Node{
    public char val;
    public Node left;
    public Node right;
    public Node(char val){
        this.val=val;
    }
}
public class TestBinaryTree {

    // 使用穷举的方式创建一棵二叉树
    public Node createTree(){
        Node A=new Node('A');
        Node B=new Node('B');
        Node C=new Node('C');
        Node D=new Node('D');
        Node E=new Node('E');
        Node F=new Node('F');
        Node G=new Node('G');
        Node H=new Node('H');
        A.left=B;
        A.right=C;
        B.left=D;
        B.right=E;
        E.right=H;
        C.left=F;
        C.right=G;
        return A;
    }

    // 前序遍历
    public void preOrderTraversal(Node root){
        if(root==null) {
            return;
        }
        System.out.print(root.val+" ");
        preOrderTraversal(root.left);
        preOrderTraversal(root.right);

    }

    // 中序遍历
    public void inOrderTraversal(Node root) {
        if (root == null) {
            return;
        }
        inOrderTraversal(root.left);
        System.out.print(root.val+" ");
        inOrderTraversal(root.right);
    }

    // 后序遍历
    public void posOrderTraversal(Node root){
        if(root==null){
            return;
        }
        posOrderTraversal(root.left);
        posOrderTraversal(root.right);
        System.out.print(root.val+" ");
    }

    // 遍历思路-求节点个数
    public static int size=0;
    public void getSize1(Node root){
        if(root==null){
            return;
        }
        size++;
        getSize1(root.left);
        getSize1(root.right);
    }

    // 子问题思路-求节点个数
    public int getSize2(Node root){
        if(root==null){
            return size;
        }
        int val=1+getSize2(root.left)+getSize2(root.right);
        return val;
    }

    // 遍历思路-求叶子节点个数
    public static int leafSize;
    public void getLeafSize1(Node root){
        if(root==null){
            return;
        }
        if(root.left==null&&root.right==null){
            leafSize++;
            return;
        }
        getLeafSize1(root.left);
        getLeafSize1(root.right);
    }

    // 子问题思路-求叶子节点个数
    public int getLeafSize2(Node root){
        if(root==null){
            return 0;
        }
        if(root.left==null&&root.right==null) {
            return 1;
        }
        int val=getLeafSize2(root.left)+getLeafSize2(root.right);
        return val;
    }

    // 第 k 层的节点个数
    public int getKLeafSize(Node root,int k){
        if(root==null){
            return 0;
        }
        if(k==1){
            return 1;
        }
        int val=getKLeafSize(root.left,k-1)+getKLeafSize(root.right, k-1);
        return val;
    }

    // 获取当前二叉树的高度
    public int getHeight(Node root){
        if(root==null){
            return 0;
        }
        return 1+Math.max(getHeight(root.left),getHeight(root.right));
    }

    // 查找二叉树的某个节点
    public Node find(Node root,char val){
        if(root==null){
            return null;
        }
        if(root.val==val){
            return root;
        }
        Node leftNode=find(root.left,val);
        if(leftNode.val==val){
            return leftNode;
        }
        Node rightNode=find(root.right,val);
        if(rightNode.val==val){
            return rightNode;
        }
        return null;
    }
}

2.7 前中后序的非递归实现

递归的实现都是在栈上进行的，如果我们要用非递归的方式实现一棵二叉树，那么我们的核心思想就是创建一个栈，并在这个栈上模拟递归。

前序遍历非递归实现

代码示例：

public void preOrderTraversal(Node root){
    if(root==null){
        return;
    }
    Stack<Node> stack=new Stack<>();
    Node cur=root;
    while(cur!=null||!stack.empty()){
        while(cur!=null){
            stack.push(cur);
            System.out.print(cur.val+" ");
            cur=cur.left;
        }
        Node top=stack.pop();
        cur=top.right;
    }
}

中序遍历非递归实现

代码示例：

public void inOrderTraversal(Node root){
    if(root==null){
        return;
    }
    Stack<Node> stack=new Stack<>(); 
    Node cur=root;
    while(cur!=null||!stack.empty()){
        while(cur!=null){
            stack.push(cur);
            cur=cur.left
        }
        Node top=stack.pop();
        System.out.print(top.val+" ");
        cur=top.right;
    }
}

后序遍历非递归实现

代码示例：

public void posOrderTraversal(Node root){
    if(root==null){
        return;
    }
    Node prev=null;
    Stack<Node> stack=new Stack<>();
    Node cur=root;
    while(cur!=null||!stack.empty()){
        while(cur!=null){
            stack.push(cur);
            cur=cur.left;
        }
        Node top=stack.peek();
        cur=top.right;
        if(cur==null||cur.val==prev.val){
            System.out.print(top.val+" ");
            prev=stack.pop();
            cur=null;
        }
    }
}

3. 二叉树练习题

3.1 二叉树基础练习题

3.1.1 二叉树的前序遍历

题目（OJ 链接）：

给你二叉树的根节点 root ，返回它节点值的前序遍历。

代码一： 子问题的思路：将左子树、右子树和根都存放进去

public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> list=new ArrayList<>();
    if(root==null){
        return list;
    }
    list.add(root.val);
    List<Integer> leftTree=preorderTraversal(root.left);
    list.addAll(leftTree);
    List<Integer> rightTree=preorderTraversal(root.right);
    list.addAll(rightTree);
    return list;
}

代码二： 遍历思路：将每个节点都遍历一遍

List<Integer> list=new ArrayList<>();
public List<Integer> preorderTraversal(TreeNode root) {
    if(root==null){
        return list;
    }
    list.add(root.val);
    preorderTraversal(root.left);
    preorderTraversal(root.right);
    return list;
}

3.1.2 二叉树的中序遍历

题目（OJ 链接）：

给定一个二叉树的根节点 root ，返回它的中序遍历。

代码一： 子问题思路

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> list=new ArrayList<>();
    if(root==null){
        return list;
    }
    List<Integer> leftTree=inorderTraversal(root.left);
    list.addAll(leftTree);
    list.add(root.val);
    List<Integer> rightTree=inorderTraversal(root.right);
    list.addAll(rightTree);
    return list;
}

代码二： 遍历思路

List<Integer> list=new ArrayList<>();
public List<Integer> inorderTraversal(TreeNode root) {
	if(root==null){
		return list;
	}
	inorderTraversal(root.left);
	list.add(root.val);
	inorderTraversal(root.right);
	return list;
}

3.1.3 二叉树的后序遍历

题目（OJ 链接）：

给定一个二叉树，返回它的后序遍历。

代码一： 子问题思

public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> list=new ArrayList<>();
    if(root==null){
        return list;
    }
    List<Integer> leftTree=postorderTraversal(root.left);
    list.addAll(leftTree);
    List<Integer> rightTree=postorderTraversal(root.right);
    list.addAll(rightTree);
    list.add(root.val);
    return list;
}

代码二： 遍历思路

List<Integer> list=new ArrayList<>();
public List<Integer> postorderTraversal(TreeNode root) {
	if(root==null){
		return list;
	}
	postorderTraversal(root.left);
	postorderTraversal(root.right);
	list.add(root.val);
	return list;
}

3.1.4 相同的树

题目（OJ 链接）：

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

代码：

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p!=null&&q==null||p==null&&q!=null){
            return false;
        }
        if(p==null&&q==null){
            return true;
        }
        if(p.val!=q.val){
            return false;
        }
        return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);
    }
}

3.1.5 另一棵树的子树

题目（OJ 链接）：

给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。

二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。

代码：

class Solution {
    public boolean isSameTree(TreeNode root,TreeNode subRoot){
        if(root!=null&&subRoot==null||root==null&&subRoot!=null){
            return false;
        }
        if(root==null&&subRoot==null){
            return true;
        }
        if(root.val!=subRoot.val){
            return false;
        }
        return isSameTree(root.left,subRoot.left)&&isSameTree(root.right,subRoot.right);
    }

    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if(root==null){
            return false;
        }
        if(isSameTree(root,subRoot)){
            return true;
        }
        if(isSubtree(root.left,subRoot)){
            return true;
        }
        if(isSubtree(root.right,subRoot)){
            return true;
        }
        return false;
    }
}

3.1.6 二叉树的最大深度

题目（OJ 链接）：

给定一个二叉树，找出其最大深度。

代码：

class Solution {
    public int maxDepth(TreeNode root) {
        if(root==null){
            return 0;
        }
        return 1+Math.max(maxDepth(root.left),maxDepth(root.right));
    }
}

3.1.7 平衡二叉树

题目（OJ 链接）：

给定一个二叉树，判断它是否是高度平衡的二叉树。

代码一： 时间复杂度为 O(N²)

class Solution {
    public int maxDepth(TreeNode root) {
        if(root==null){
            return 0;
        }
        return 1+Math.max(maxDepth(root.left),maxDepth(root.right));
    }

    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);
    }
}

代码二： 时间复杂度为 O(N)

class Solution {
    public int maxDepth(TreeNode root) {
        if(root==null){
            return 0;
        }
        int leftDepth=maxDepth(root.left);
        int rightDepth=maxDepth(root.right);
        if(leftDepth>=0&&rightDepth>=0&&Math.abs(leftDepth-rightDepth)<=1){
            return 1+Math.max(leftDepth,rightDepth);
        }else{
            return -1;
        }
    }
    public boolean isBalanced(TreeNode root) {
        return maxDepth(root)>=0;
    }
}

3.1.8 对称二叉树

题目（OJ 链接）：

给定一个二叉树，检查它是否是镜像对称的。

代码：

class Solution {
    public boolean isSymmetricChild(TreeNode leftTree,TreeNode rightTree) {
        if(leftTree==null&&rightTree==null){
            return true;
        }
        if(leftTree!=null&&rightTree==null||leftTree==null&&rightTree!=null){
            return false;
        }
        if(leftTree.val!=rightTree.val){
            return false;
        }
        return isSymmetricChild(leftTree.left,rightTree.right)&&isSymmetricChild(leftTree.right,rightTree.left);
    }

    public boolean isSymmetric(TreeNode root) {
        if(root==null){
            return false;
        }
        return isSymmetricChild(root.left,root.right);
    }
}

3.2 二叉树进阶练习题

3.2.1 二叉树的构建及遍历

题目（OJ 链接）：

编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。例如如下的先序遍历字符串： ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。

代码：

class TreeNode{
    public char val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(char val){
        this.val=val;
    }
}

public class Main{
    public static int i=0;
    public static TreeNode createBinaryTree(String str){
        if(str.length()==0){
            return null;
        }
        TreeNode root=null;
        if(str.charAt(i)=='#'){
            i++;
        }else{
            root=new TreeNode(str.charAt(i));
            i++;
            root.left=createBinaryTree(str);
            root.right=createBinaryTree(str);
        }
        return root;
    }
    
    public static void inOrderTraversal(TreeNode root){
        if(root==null){
            return;
        }
        inOrderTraversal(root.left);
        System.out.print(root.val+" ");
        inOrderTraversal(root.right);
    }
    
    public static void main(String[] args){
        Scanner scan=new Scanner(System.in);
        while(scan.hasNext()){
            String str=scan.nextLine();
            TreeNode ret=createBinaryTree(str);
            inOrderTraversal(ret);
            System.out.println();
        }
        
    }
}

3.2.2 二叉树的层序遍历

题目（OJ 链接）：

给你一个二叉树，请你返回其按 层序遍历 得到的节点值。（即逐层地，从左到右访问所有节点）。

代码：

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ret=new ArrayList<>();
        if(root==null){
            return ret;
        }
        Queue<TreeNode> queue =new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            int size=queue.size();
            List<Integer> list=new ArrayList<>();
            while(size>0){
                TreeNode top=queue.poll();
                list.add(top.val);
                if(top.left!=null){
                    queue.offer(top.left);
                }
                if(top.right!=null){
                    queue.offer(top.right);
                }
                size--;
            }
            ret.add(list);
        }
        return ret;
    }
}

3.2.3 二叉树的最近公共祖先

题目（OJ 链接）：

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

代码：

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null){
            return null;
        }
        if(root==p||root==q){
            return root;
        }
        TreeNode left=lowestCommonAncestor(root.left,p,q);
        TreeNode right=lowestCommonAncestor(root.right,p,q);
        if(left!=null&&right==null){
            return left;
        }
        if(left==null&&right!=null){
            return right;
        }
        if(left==null&&right==null){
            return null;
        }
        return root;
    }
}

3.2.4 二叉搜索树与双向链表

题目（OJ 链接）：

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。

代码：

public class Solution {
    public TreeNode prev;
    public void ConvertChild(TreeNode pCur) {
        if(pCur==null){
            return;
        }
        ConvertChild(pCur.left);
        pCur.left=prev;
        if(prev!=null){
            prev.right=pCur;
        }
        prev=pCur;
        ConvertChild(pCur.right);
    }
    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree==null){
            return null;
        }
        ConvertChild(pRootOfTree);
        TreeNode head=pRootOfTree;
        while(head.left!=null){
            head=head.left;
        }
        return head;
    }
}

补充：

二叉搜索树特点： 左孩子比根节点小，右孩子比根节点大

3.2.5 从前序与中序遍历序列构造二叉树

题目（OJ 链接）：

给定一棵树的前序遍历 preorder 与中序遍历 inorder。请构造二叉树并返回其根节点。

代码：

class Solution {
    public int prevIndex=0;
    public TreeNode buildTreeChild(int[] preorder, int[] inorder, int inBegin, int inEnd) {
        if(inBegin>inEnd){
            return null;
        }
        TreeNode root=new TreeNode(preorder[prevIndex]);

        int index=findIndex(inorder,inBegin,inEnd,root.val);
        prevIndex++;
        root.left=buildTreeChild(preorder,inorder,inBegin,index-1);
        root.right=buildTreeChild(preorder,inorder,index+1,inEnd);
        return root;    
    }
    public int findIndex(int[] inorder,int inBegin,int inEnd,int k){
        for(int i=inBegin;i<=inEnd;i++){
            if(k==inorder[i]){
                return i;
            }
        }
        return -1;
    }
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder==null||inorder==null){
            return null;
        }
        return buildTreeChild(preorder,inorder,0,inorder.length-1);
    }
}

3.2.6 从中序与后序遍历序列构造二叉树

题目（OJ 链接）：

根据一棵树的中序遍历与后序遍历构造二叉树。

代码：

class Solution {
    public int rear;
    public TreeNode buildTreeChild(int[] inorder, int inBegin, int inEnd, int[] postorder) {
        if(inBegin>inEnd){
            return null;
        }
        TreeNode root=new TreeNode(postorder[rear]);
        int index=findIndex(inorder,inBegin,inEnd,postorder[rear]);
        rear--;
        root.right=buildTreeChild(inorder,index+1,inEnd,postorder);
        root.left=buildTreeChild(inorder,inBegin,index-1,postorder);
        return root;
    }
    public int findIndex(int[] inorder,int inBegin, int inEnd, int k){
        for(int i=inBegin;i<=inEnd;i++){
            if(inorder[i]==k){
                return i;
            }
        }
        return -1;
    }
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        rear=postorder.length-1;
        return buildTreeChild(inorder,0,inorder.length-1,postorder);
    }
}

3.2.7 根据二叉树创建字符串

题目（OJ 链接）：

你需要采用前序遍历的方式，将一个二叉树转换成一个由括号和整数组成的字符串。

空节点则用一对空括号 “()” 表示。而且你需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。

代码：

class Solution {
    public void tree2strChild(TreeNode root,StringBuilder sb){
        if(root==null){
            return;
        }
        sb.append(""+root.val);
        if(root.left==null){
            if(root.right==null){
                return;
            }else{
                sb.append("()");
            }
        }else{
            sb.append("(");
            tree2strChild(root.left,sb);
            sb.append(")");
        }
        if(root.right==null){
            return;
            
        }else{
            sb.append("(");
            tree2strChild(root.right,sb);
            sb.append(")");
        }
    }
    public String tree2str(TreeNode root) {
        if(root==null){
            return null;
        }
        StringBuilder sb=new StringBuilder();
        tree2strChild(root,sb);
        return sb.toString();
    }
}