树型结构

概念

树是一种非线性的的数据结构，它是由n(n>=0)个有限结点组成一个具有层次关系的集合，将它叫做树是因为看它起来像一棵倒挂的树，也就是根朝上，叶朝下。它具有以下特点：

• 有一个特殊的结点，称为根节点，根节点没有前驱节点
• 除根节点外，其余节点被分成M(M > 0)个互不相交的集合T1、T2、······、Tm，其中每一个集合Ti(1 <= i <= m)又是一棵与树类似的子树。每棵子树的根节点有且只有一个前驱，可以有0个或多个后继
• 树是递归定义的。

注意：
树形结构中，子树之间不能有交集的，否则就不是树形结构，子树是不相交的；
除了根节点外，每个结点有且仅有一个父结点；
一棵N个结点的树有N - 1 条边。

相关概念

结点的度：一个结点含有子树的个数称为该结点的度；如上图：A的度为3
树的度：一棵树中，所有结点度的最大值称为树的度；如上图：树的度为3
叶子结点或终端结点：度为0的结点称为叶结点；如上图：F、H、I、J、K、L为叶结点
双亲结点或父结点：若一个结点含有子结点，则这个结点称为其子结点的父结点；如上图：A是B的父结点
孩子结点或子结点：一个结点含有的子树的根节点称为该结点的子结点；如上图：B是A的孩子结点
根结点：一棵树中，没有双亲结点的结点；如上图：A
结点的层次：从根开始定义起，根为第1层，根的子结点为第2层，以此类推
树的高度或深度：树中结点的最大层次；如上图：树的高度为4
非终端结点或分支结点：度不为0的结点；如上图：B、C、D、E…等结点为分支结点
兄弟结点：具有相同父结点的结点互称为兄弟结点；如上图：B、C是兄弟结点
堂兄弟结点：双亲在同一层的结点互为堂兄弟；如上图：F、G是堂兄弟结点
结点的祖先：从根到该结点所经分支上的所有结点；如上图：A是所有结点的祖先
子孙：以某结点为根的子树中任一结点都称为该结点的子孙。如上图：所有结点都是A的子孙
森林：由m(m>=0)棵互不相交的树组成的集合称为森林

树的表示形式

树结构相对线性表就比较复杂了，要存储起来比较麻烦，实际中树有很多种表示形式，如：双亲表示法，孩子表示法，孩子双亲表示法，孩子兄弟表示法等等，先简单了解其中最常用的孩子兄弟表示法。

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

树的应用

文件系统管理(目录和文件)

二叉树

概念

一棵二叉树是结点的一个有限集合，该集合：

1. 或者为空
2. 或者是由一个根结点加上两棵分别称为左子树和右子树的二叉树组成。

从上图可以看出：

1. 二叉树不存在度为大于2的结点
2. 二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树

注意：对于任意的二叉树都是由以下几种情况复合而成的：

两种特殊的二叉树

• 满二叉树：一棵二叉树，如果每层的结点数都达到最大值，则这棵二叉树就是满二叉树，也就是说，如果一棵二叉树的层数为K，且结点总数是2^k - 1，则它就是满二叉树。
• 完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的，对于深度为K的，由n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从0至n-1的结点一一对应时称之为完全二叉树。注意：满二叉树是一种特殊的完全二叉树。
  -

二叉树的性质

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

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

3. 对任何一棵二叉树，如果其叶结点个数为 n0，度为2的非叶结点个数为 n2，则有n0 = n2 + 1
   

4. 具有n个结点的完全二叉树的深度k为${\log }_2(n+1)$向上取整
   

5. 对于具有n个结点的完全二叉树，如果按照从上至下，从左至右的顺序对所有结点从0开始编号，则对于序号为 i 的结点有：
   若 i > 0，双亲序号：(i - 1) / 2; i = 0，i 为根节点编号，无双亲结点
   若 2i + 1 < n ，左孩子序号：2i + 1，否则无左孩子
   若 2i + 2 < n ，右孩子序号：2i + 2，否则无右孩子
   

1.某二叉树共有 399 个结点，其中有 199 个度为 2 的结点，则该二叉树中的叶子结点数为（ ）
A 不存在这样的二叉树
B 200
C 198
D 199
答案：B

2.在具有 2n 个结点的完全二叉树中，叶子结点个数为（ ）
A n
B n+1
C n-1
D n/2
答案：A

3.一个具有767个节点的完全二叉树，其叶子节点个数为（）
A 383
B 384
C 385
D 386
答案：B

4.一棵完全二叉树的节点数为531个，那么这棵树的高度为（ ）
A 11
B 10
C 8
D 12
答案：B
具有n个结点的完全二叉树的深度k为${\log }_2(n+1)$向上取整
${\log }_2(531+1)$ = ${\log }_{2}532$
${\log }_{2}512$ < ${\log }_{2}532$ < ${\log }_{2}1024$
9 < k < 10

二叉树的存储

二叉树的存储结构分为：顺序存储和类似于链表的链式存储
二叉树的链式存储是通过一个一个结点的引用起来的，常见的方式有二叉和三叉表示方式，具体如下：

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

二叉树的基本操作

前置说明

在学习二叉树的基本操作之前，需要先创建一棵二叉树，然后才能学习其相关的基本操作，先在此处手动快速创建一棵简单的二叉树，方便快速进入二叉树操作学习，后续我们再研究二叉树真正的创建方式

public class BinaryTree {static class TreeNode{public TreeNode left;public TreeNode right;public int val;public TreeNode(int val) {this.val = val;}}public TreeNode createBinaryTree(){TreeNode node1 = new TreeNode(1);TreeNode node2 = new TreeNode(2);TreeNode node3 = new TreeNode(3);TreeNode node4 = new TreeNode(4);TreeNode node5 = new TreeNode(5);TreeNode node6 = new TreeNode(6);node1.left = node2;node1.right = node4;node2.left = node3;node4.left = node5;node4.right = node6;return node1;}
}

二叉树的遍历

1. 前中后序遍历
   学习二叉树结构，最简单的方式就是遍历，所谓遍历(Traversal)是沿着某条搜索路线，依次对树中每个结点均做一次且做一次的访问。访问结点所做的操作依赖于具体的应用问题(比如：打印结点内容、结点内容加1)。遍历时二叉树上最重要的操作之一，是二叉树上进行其他运算的基础。
   在遍历二叉树时，如果没有进行某种约定，每个人都按照自己的方式遍历，得出的结果比较混乱，如果按照某种规则进行约定，则每个人对于同一棵树的遍历结果肯定是相同的。如果N代表根节点，L代表根节点的左子树，R代表根节点的右子树，则根据遍历根节点的先后次序有以下遍历方式：

• • NLR：前序遍历(Preorder Traversal亦称先序遍历)——访问根节点–>根的左子树–>根的右子树。
• • LLR：中序遍历(Inorder Traversal)——根的左子树–>根节点–>根的右子树。
• • LRN：后序遍历(Postorder Traversal)——根的左子树–>根的右子树–>根节点。

//前序遍历
void preOrder(Node root);//中序遍历
void inOrder(Node root);//后序遍历
void postOrder(Node root);

此时打印了：1，2，3

此时打印了：1，2，3

此时打印了：1，2，3

此时打印了1，2，3，4，5

此时打印了：1，2，3，4，5

此时打印了1，2，3，4，5，6

此时打印：1，2，3，4，5，6
前序遍历结果为1，2，3，4，5，6

此时并没有打印

此时打印：3

此时打印：3，2

此时打印：3，2

此时打印：3，2，1

此时打印：3，2，1

此时打印：3，2，1，5

此时打印：3，2，1，5

此时打印：3，2，1，5，4

此时打印：3，2，1，5，4

此时打印：3，2，1，5，4，6

此时打印：3，2，1，5，4，6
中序遍历结果为3，2，1，5，4，6

此时并没有打印内容

此时并没有打印内容

此时打印：3

此时打印：3

此时打印：3，2

此时打印：3，2
此时打印：3，2

此时打印：3，2

此时打印：3，2，5

此时打印：3，2，5

此时打印：3，2，5

此时打印：3，2，5

此时打印：3，2，5，6

此时打印：3，2，5，6，4

此时打印：3，2，5，6，4，1
后序遍历结果为3，2，5，6，4，1

2. 层序遍历
   层序遍历：除了先序遍历、中序遍历、后序遍历外，还可以对二叉树进行层序遍历。设二叉树的根节点所在层数为1，层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第二层上的结点，接着是第三层的结点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历
   

接下来通过例子再加强我们对其的理解

1.某完全二叉树按层次输出（同一层从左到右）的序列为 ABCDEFGH 。该完全二叉树的前序序列为()
A: ABDHECFG B: ABCDEFGH C: HDBEAFCG D: HDEBFGCA
答案：A
2.二叉树的先序遍历和中序遍历如下：先序遍历：EFHIGJK;中序遍历：HFIEJKG.则二叉树根结点为()
A: E B: F C: G D: H答案为：A
3.设一课二叉树的中序遍历序列：badce，后序遍历序列：bdeca，则二叉树前序遍历序列为()
A: adbce B: decab C: debac D: abcde

答案为：D
4.某二叉树的后序遍历序列与中序遍历序列相同，均为 ABCDEF ，则按层次输出(同一层从左到右)的序列为()
A: FEDCBA B: CBAFED C: DEFCBA D: ABCDEF

答案为：A

接下来是代码实现：

public class BinaryTree {static class TreeNode{public TreeNode left;public TreeNode right;public int val;public TreeNode(int val) {this.val = val;}}public TreeNode createBinaryTree(){TreeNode node1 = new TreeNode(1);TreeNode node2 = new TreeNode(2);TreeNode node3 = new TreeNode(3);TreeNode node4 = new TreeNode(4);TreeNode node5 = new TreeNode(5);TreeNode node6 = new TreeNode(6);node1.left = node2;node1.right = node4;node2.left = node3;node4.left = node5;node4.right = node6;return node1;}// 前序遍历void preOrder(TreeNode root){if(root == null){return;}System.out.print(root.val + " ");preOrder(root.left);preOrder(root.right);}
}

public class Test {public static void main(String[] args) {BinaryTree tree = new BinaryTree();BinaryTree.TreeNode root = tree.createBinaryTree();tree.preOrder(root);//结果为：//1 2 3 4 5 6}
}

// 中序遍历
void inOrder(TreeNode root){if(root == null){return;}inOrder(root.left);System.out.print(root.val + " ");inOrder(root.right);
}// 后序遍历
void postOrder(TreeNode root){if(root == null){return;}postOrder(root.left);postOrder(root.right);System.out.print(root.val + " ");
}

public class Test {public static void main(String[] args) {BinaryTree tree = new BinaryTree();BinaryTree.TreeNode root = tree.createBinaryTree();tree.inOrder(root);System.out.println();tree.postOrder(root);//结果为：//3 2 1 5 4 6//3 2 5 6 4 1}
}

接下来给出三道遍历的OJ题

1. 前序遍历

class Solution {public List<Integer> preorderTraversal(TreeNode root) {}
}

可以看到方法的返回值是是一个链表
对于此，有两种解决方法：

• 遍历二叉树的每个结点，只要不为空就加入链表，链表对象为类变量，创建在方法外
• 链表对象创建在方法内，将此问题用子问题来解决，将根节点加入链表，将左子树加入链表，将右子树加入链表

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

class Solution {public List<Integer> preorderTraversal(TreeNode root) {List<Integer> list = new LinkedList<>();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;}
}

2. 中序遍历

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

class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> list = new LinkedList<>();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;}
}

3. 后序遍历

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

class Solution {public List<Integer> postorderTraversal(TreeNode root) {List<Integer> list = new LinkedList<>();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;}
}

二叉树的基本操作

// 获取树中节点的个数
public int size(Node root);
// 获取叶子节点的个数
public int getLeafNodeCount(Node root);
// 子问题思路-求叶子结点个数
// 获取第K层节点的个数
public int getKLevelNodeCount(Node root,int k);
// 获取二叉树的高度
public int getHeight(Node root);
// 检测值为value的元素是否存在
public Node find(Node root, int val);
//层序遍历
public void levelOrder(Node root);
// 判断一棵树是不是完全二叉树
public boolean isCompleteTree(Node root);

• 获取树中节点的个数
  依然有两种解决思路：

1. 遍历二叉树，只要根结点不为空 ++
2. 子问题：整棵树有多少个结点 = 左子树的结点 + 右子树的结点 + 1

public int nodeSize = 0;
public void size(TreeNode root){if(root == null){return;}nodeSize++;size(root.left);size(root.right);
}

public class Test {public static void main(String[] args) {BinaryTree tree = new BinaryTree();BinaryTree.TreeNode root = tree.createBinaryTree();tree.size(root);System.out.println(tree.nodeSize);}
}
//结果为6

第二种思路：

public int size(TreeNode root){if(root == null){return 0;}return size(root.left) + size(root.right) + 1;
}

public class Test {public static void main(String[] args) {BinaryTree tree = new BinaryTree();BinaryTree.TreeNode root = tree.createBinaryTree();System.out.println(tree.size(root));}
}
//结果为：6

• 获取叶子节点的个数
  什么是叶子结点
  没有左子树和右子树的结点为叶子结点
  同样用两种思路来解决
  第一种思路：遍历二叉树，找到所有叶子节点

public int leafNodeSize = 0;
public void getLeafNodeCount(TreeNode root){if(root == null){return;}if(root.left == null && root.right == null){leafNodeSize++;}getLeafNodeCount(root.left);getLeafNodeCount(root.right);
}

public class Test {public static void main(String[] args) {BinaryTree tree = new BinaryTree();BinaryTree.TreeNode root = tree.createBinaryTree();tree.getLeafNodeCount(root);System.out.println(tree.leafNodeSize);}
}
//结果为：3

第二种思路：二叉树的叶子节点 = 左子树的叶子结点 + 右子树的叶子节点

public int getLeafNodeCount(TreeNode root){if(root == null){return 0;}if(root.left == null && root.right == null){return 1;}return getLeafNodeCount(root.left) + getLeafNodeCount(root.right);
}

public class Test {public static void main(String[] args) {BinaryTree tree = new BinaryTree();BinaryTree.TreeNode root = tree.createBinaryTree();System.out.println(tree.getLeafNodeCount(root));}
}
//结果为：3

• 获取第K层节点的个数

// 获取第K层节点的个数
public int getKLevelNodeCount(TreeNode root,int k){if(root == null){return 0;}if(k == 1){return 1;}return getKLevelNodeCount(root.left,k-1) + getKLevelNodeCount(root.right,k-1);
}

public class Test {public static void main(String[] args) {BinaryTree tree = new BinaryTree();BinaryTree.TreeNode root = tree.createBinaryTree();System.out.println(tree.getKLevelNodeCount(root,3));}
}
//结果为：3

• 获取二叉树的高度
  获取二叉树的高度
  子问题思路：左子树的高度和右子树的高度两者的最大值 + 1

/*时间复杂度：O(N)空间复杂度：O(以2为底的logN)*/
//获取二叉树的高度
public int getHeight(TreeNode root){if(root == null){return 0;}//int leftTreeHeight = getHeight(root.left);//int rightTreeHeight = getHeight(root.right);//return Math.max(leftTreeHeight,rightTreeHeight) + 1;return Math.max(getHeight(root.left),getHeight(root.right)) + 1;//int leftTreeHeight = getHeight(root.left);//int rightTreeHeight = getHeight(root.right);//return leftTreeHeight > rightTreeHeight ? leftTreeHeight+1 : rightTreeHeight+1;//这种返回方法在OJ题中是会超出时间限制的，因为树越大，递归的次数多，时间越长//return getHeight(root.left) > getHeight(root.right) ? getHeight(root.left)+1 : getHeight(root.right)+1;
}

public class Test {public static void main(String[] args) {BinaryTree tree = new BinaryTree();BinaryTree.TreeNode root = tree.createBinaryTree();System.out.println(tree.getHeight(root));}
}
//结果为：3

• 检测值为value的元素是否存在
  判断根节点是不是val   不是
  那就判断左子树   不是
  那就判断右子树   不是
  左子树和右子树都没有，那么证明这棵树没有这个数字

/*
时间复杂度：O(N)
空间复杂度：O(以2为底的logN)
*/
// 检测值为value的元素是否存在
public TreeNode find(TreeNode root, int val){if(root == null){return null;}if(root.val == val){return root;}TreeNode leftTree = find(root.left,val);if(leftTree != null){return leftTree;}TreeNode rightTree = find(root.right,val);if(rightTree != null){return rightTree;}return null;
}

public class Test {public static void main(String[] args) {BinaryTree tree = new BinaryTree();BinaryTree.TreeNode root = tree.createBinaryTree();BinaryTree.TreeNode find = tree.find(root,5);System.out.println(find.val);}
}
//结果为：5

• 层序遍历
  

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

public class Test {public static void main(String[] args) {BinaryTree tree = new BinaryTree();BinaryTree.TreeNode root = tree.createBinaryTree();tree.levelOrder(root);}//结果为：1 2 4 3 5 6 
}

层序遍历
对于该OJ题，返回值是二维数组

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public List<List<Integer>> levelOrder(TreeNode root) {}
}

只需在每次进入循环建立一个数组，并统计此时队列的大小，然后将这个大小个数的元素放进去数组，就是这一层的个数

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> list1 = new ArrayList<>();if(root == null){return list1;}Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);while(!queue.isEmpty()){List<Integer> list2 = new ArrayList<>();int size = queue.size();while(size > 0){TreeNode cur = queue.poll();list2.add(cur.val); if(cur.left != null){queue.offer(cur.left);}if(cur.right != null){queue.offer(cur.right);}size--;}list1.add(list2);}return list1;}
}

• 判断一棵树是不是完全二叉树
  

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

二叉树相关OJ题

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

/*
假设 p的结点数为m，q的结点数为n
时间复杂度为O(min(m,n))
*/
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);}
}

2. 另一棵树的子树
   给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。
   二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。
   

/*
假设 root的结点数为r，subRoot的结点数为s
时间复杂度为O(r * s)*/
class Solution {public boolean isSubtree(TreeNode root, TreeNode subRoot) {if(root == null){return false;}if(isSameTree(root, subRoot)){return true;}return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);}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. 翻转二叉树
   给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
   
   

class Solution {public TreeNode invertTree(TreeNode root) {if(root == null){return null;}TreeNode tmp = root.left;root.left = root.right;root.right = tmp;invertTree(root.left);invertTree(root.right);return root;}
}

4. 对称二叉树
   给你一个二叉树的根节点 root ， 检查它是否轴对称。
   
   

class Solution {public boolean isSymmetric(TreeNode root) {if(root == null){return true;}return isSymmetricChild(root.left,root.right);        }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);}
}

5. 平衡二叉树
   给定一个二叉树，判断它是否是 平衡二叉树
   平衡二叉树 是指该树所有节点的左右子树的深度相差不超过 1。
   
   
   

/*
时间复杂度为：O(N^2)*/
class Solution {public boolean isBalanced(TreeNode root) {if(root == null){return true;}int leftHeight = getHeight(root.left);int rightHeight = getHeight(root.right);if(Math.abs(leftHeight - rightHeight) >= 2){return false;}return isBalanced(root.left) && isBalanced(root.right);}public int getHeight(TreeNode root){if(root == null){return 0;}return Math.max(getHeight(root.left),getHeight(root.right)) + 1;       }
}

上述代码算法的时间复杂度为O(N²)，因为我们每遍历一个结点，都需要算一下左右子树的高度，求左右子树的高度，我们也是遍历每个结点，这样最后算出的时间复杂度是O(N²)
那有什么办法让时间复杂度为O(N)呢
其实在算高度的时候我们已经把每个结点的深度算出来，并返回去在取出最大值加一，可以在这个返回过程前进行判断，如果两者之差大于等于2，返回-1，下一次检测到小于0，则继续返回-1，这样就可以通过最后返回值是否是>=0来判断是不是平衡二叉树

class Solution {public boolean isBalanced(TreeNode root) {if(root == null){return true;}return getHeight(root) >= 0;}public int getHeight(TreeNode root){if(root == null){return 0;}int leftTreeHeight = getHeight(root.left);if(leftTreeHeight < 0){return -1;}int rightTreeHeight = getHeight(root.right);if(rightTreeHeight < 0){return -1;}if(Math.abs(leftTreeHeight - rightTreeHeight) >= 2){return -1;}else{return Math.max(leftTreeHeight,rightTreeHeight) + 1; }          }
}

6. 二叉搜索树与双向链表
   二叉搜索树（BST，Binary Search Tree），也称二叉排序树或二叉查找树。
   二叉搜索树：一棵二叉树，可以为空；如果不为空，满足以下性质：
   非空左子树的所有键值小于其根结点的键值。
   非空右子树的所有键值大于其根结点的键值。
   左、右子树都是二叉搜索树。
   
   输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。
   
   

import java.util.*;
/**
public class TreeNode {int val = 0;TreeNode left = null;TreeNode right = null;public TreeNode(int val) {this.val = val;}}
*/
public class Solution {public TreeNode Convert(TreeNode root) {if(root == null){return null;}ConvertChlid(root);//返回链表的第一个结点while(root.left != null){root = root.left;}return root;}public TreeNode prev = null;public void ConvertChlid(TreeNode root) {if(root == null){return;}ConvertChlid(root.left);root.left = prev;if(prev != null){prev.right = root;}prev = root;ConvertChlid(root.right);}
}

7. 二叉树的构建及遍历
   编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。 例如如下的先序遍历字符串： ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。
   可能有多组测试数据，对于每组数据， 输出将输入字符串建立二叉树后中序遍历的序列，每个字符后面都有一个空格。 每个输出结果占一行。
   

import java.util.Scanner;class TreeNode{public char val;public TreeNode left;public TreeNode right;public TreeNode(char val){this.val = val;}
}// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {public int i = 0;public TreeNode createTree(String str){if(str.charAt(i) != '#'){TreeNode node = new TreeNode(str.charAt(i));i++;node.left = createTree(str);node.right = createTree(str);return node;}else{i++;}return null;}public void inOrder(TreeNode root){if(root == null){return;}inOrder(root.left);System.out.print(root.val + " ");inOrder(root.right);}public static void main(String[] args) {Scanner in = new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseString str = in.nextLine();Main main = new Main();TreeNode root = main.createTree(str);main.inOrder(root);}}
}

后面以此类推

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

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode(int x) { val = x; }* }*/
class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if(root == null){return null;}if(p == root || q == root){return root;}TreeNode leftTree = lowestCommonAncestor(root.left, p, q);TreeNode rightTree = lowestCommonAncestor(root.right, p, q);if(leftTree != null && rightTree != null){return root;}else if(leftTree != null){return leftTree;}else{return rightTree;}}
}

还有另一种方法：

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode(int x) { val = x; }* }*/
class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if(root == null){return null;}Stack<TreeNode> stackP = new Stack<>();Stack<TreeNode> stackQ = new Stack<>();getPath(root, p, stackP);getPath(root, q, stackQ);int sizeP = stackP.size();int sizeQ = stackQ.size();if(sizeP > sizeQ){int size = sizeP - sizeQ;while(size > 0){stackP.pop();size--;}}else{int size = sizeQ - sizeP;while(size > 0){stackQ.pop();size--;}}while(!stackP.empty() && !stackQ.empty()){if(stackP.peek() == stackQ.peek()){return stackP.pop();}stackP.pop();stackQ.pop();}return null;}private boolean getPath(TreeNode root, TreeNode node, Stack<TreeNode> stack){if(root == null){return false;}stack.push(root);if(root == node){return true;}boolean ret1 = getPath(root.left, node, stack);if(ret1){return true;}boolean ret2 = getPath(root.right, node, stack);if(ret2){return true;}stack.pop();return false;}
}

9. 从前序与中序遍历序列构造二叉树
   给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
   
   

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public int preIndex = 0;public TreeNode buildTree(int[] preorder, int[] inorder) {return buildTreeChild(preorder,inorder,0,inorder.length-1);}public TreeNode buildTreeChild(int[] preorder, int[] inorder, int inorderBegin, int inorderEnd) {for(int i = inorderBegin; i <= inorderEnd; i++){if(inorder[i] == preorder[preIndex]){TreeNode node = new TreeNode(inorder[i]);preIndex++;node.left = buildTreeChild(preorder, inorder, inorderBegin, i-1);node.right = buildTreeChild(preorder, inorder, i + 1, inorderEnd);return node;}}return null;}
}

10. 从中序与后序遍历序列构造二叉树
    给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。
    

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public int postIndex;public TreeNode buildTree(int[] inorder, int[] postorder) {postIndex = postorder.length-1;return buildTreeChild(inorder, postorder, 0, inorder.length-1);}public TreeNode buildTreeChild(int[] inorder, int[] postorder, int inorderBegin, int inorderEnd) {for(int i = inorderBegin; i <= inorderEnd; i++){if(inorder[i] == postorder[postIndex]){TreeNode node = new TreeNode(inorder[i]);postIndex--;node.right = buildTreeChild(inorder, postorder, i + 1, inorderEnd);node.left = buildTreeChild(inorder, postorder, inorderBegin, i-1);return node;}}return null;}
}

11. 根据二叉树创建字符串
    给你二叉树的根节点 root ，请你采用前序遍历的方式，将二叉树转化为一个由括号和整数组成的字符串，返回构造出的字符串。
    空节点使用一对空括号对 “()” 表示，转化后需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。
    

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public String tree2str(TreeNode root) {StringBuilder stb = new StringBuilder();tree2strChild(root, stb);return stb.toString();}public void tree2strChild(TreeNode root, StringBuilder stb) {if(root == null){return;}stb.append(root.val);if(root.left != null){stb.append("(");tree2strChild(root.left,stb);stb.append(")");}else{if(root.right == null){return;}else{stb.append("()");}}if(root.right != null){stb.append("(");tree2strChild(root.right,stb);stb.append(")");}else{return;}}
}

12. 二叉树前序非递归遍历实现
    

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public List<Integer> preorderTraversal(TreeNode root) {List<Integer> list = new LinkedList<>();if(root == null){return list;}TreeNode cur = root;Stack<TreeNode> stack = new Stack<>();while(cur != null || !stack.empty()){while(cur != null){list.add(cur.val);stack.push(cur);cur = cur.left;}TreeNode top = stack.pop();cur = top.right;}return list;}
}

13. 二叉树中序非递归遍历实现
    

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> list = new LinkedList<>();if(root == null){return list;}TreeNode cur = root;Stack<TreeNode> stack = new Stack<>();while(cur != null || !stack.empty()){while(cur != null){stack.push(cur);cur = cur.left;}TreeNode top = stack.pop();list.add(top.val);cur = top.right;}return list;}
}

14. 二叉树后序非递归遍历实现
    

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public List<Integer> postorderTraversal(TreeNode root) {List<Integer> list = new LinkedList<>();if(root == null){return list;}TreeNode cur = root;Stack<TreeNode> stack = new Stack<>();TreeNode prev = null;while(cur != null || !stack.empty()){while(cur != null){stack.push(cur);cur = cur.left;}TreeNode top = stack.peek();if(top.right == null || top.right == prev) {stack.pop();list.add(top.val);prev = top;}else {cur = top.right;}}return list;}
}

---

关于二叉树的学习，先了解到这里。希望这篇文章对您有帮助！！！