二叉树--DS

1. 树

1.1 树的定义

树是一种非线性的数据结构，它是由n (n >= 0)个有限结点组成的一个具有层次关系的集合。之所以将它称为“树”，是因为它像一颗倒挂起来的树，也就是说它是根朝上，叶子在下的。

参考上面的图片，我们需要注意到：

1. 树有一个特殊的结点–根节点，根节点没有前驱结点
2. 除了根节点外，其他结点可以被分成多个不可交互的集合，构成与树类似的子树，每颗子树的根节点有且只有一个前驱，但是可以有0个或多个后继。
3. 树型结构中，子树间不能有交集，换句话说就是子树间不能构成回环，否则就不是树形结构。

1.2 树的相关概念

以上面树为例说明：

• 结点的度：一个结点含有子树的个数称为该结点的度； 如上图：A的度为6
• 树的度：一棵树中，所有结点度的最大值称为树的度； 如上图：树的度为6
• 叶子结点：度为0的结点称为叶结点； 如上图：B、C、H、I…等节点为叶结点
• 父结点：若一个结点含有子结点，则这个结点称为其子结点的父结点； 如上图：A是B的父结点
• 孩子结点：一个结点含有的子树的根结点称为该结点的子结点； 如上图：B是A的孩子结点
• 根结点：一棵树中，没有双亲结点的结点；如上图：A
• 结点的层次：从根开始定义起，根为第1层，根的子结点为第2层，以此类推
• 树的高度或深度：树中结点的最大层次； 如上图：树的高度为4

2. 二叉树

2.1 二叉树的定义

一棵二叉树是结点的有限集合，该集合是由一个根节点加上两颗被称为左子树和右子树的二叉树构成。也可由一个空集合构成。
根据名字可以所谓二叉树就是树中不存在度大于2的结点，二叉树的子树有左右之分，次序不能颠倒，因此二叉树也是一颗有序树。也就是说二叉树的结构可以看成是以下几种情况复合而成的：

二叉树中存在两种特殊的二叉树需要我们去了解，满二叉树和完全二叉树。需要注意的是满二叉树其实也是一种特殊情况的完全二叉树。

2.1.1 满二叉树

对于一颗二叉树而言，如果每层的结点树都达到最大值，则这棵二叉树就是满二叉树。换成数学语言来解释就是，一颗存在K层的二叉树，结点总数是2^k - 1,根为第一层。

2.1.2 完全二叉树

对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从0至n-1的结点一一对应时称之为完全二叉树，也就是说一棵从上到下、从左到右都是连续结点的二叉树叫做完全二叉树。

2.2 二叉树的性质

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为Log2(n+1)向上取整。
5. 对于具有n个结点的完全二叉树，如果按照从上至下从左至右的顺序对所有节点从0开始编号，则对于序号为i的结点有：

• 若i>0，父节点序号：(i-1)/2；当i=0时，i为根节点无父节点
• 若2i+1< n,左孩子序号为：2i+1；若2i+1>= n时，左孩子不存在
• 若2i+2< n,右孩子序号为：2i+1；若2i+2>= n时，右孩子不存在

2.3 二叉树的组织结构

我们组织二叉树的结构通常是采用链式存储，即通过链表的形式来组织二叉树的一个一个结点，我们常见的二叉树有两种表示方法：

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

2.4 二叉树的基本操作

我们这里保存下二叉树中常见的操作:

// 获取树中节点的个数:根节点+左子树节点数+右子树节点数  
public int size(TreeNode root) {  if(root == null) {  return 0;  }  return size(root.left) + size(root.right) + 1;  
}// 获取叶子节点的个数:左子树叶子节点数 + 右子树叶子节点数  
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);  }// 获取第K层节点的个数:左子树第k-1层节点数+右子树第k-1层节点数  
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);  
}// 获取二叉树的高度：左右子树最大高度 + 1（根节点）  
public int getHeight(TreeNode root) {  if(root == null) {  return 0;  }  int leftHeight = getHeight(root.left);  int rightHeight = getHeight(root.right);  return Math.max(leftHeight,rightHeight) + 1;  }// 检测值为value的元素是否存在:检查根节点，根节点不是再到左子树找，左子树找不到就到右子树找，都找不到就没有  
public TreeNode find(TreeNode root, char val) {  if(root == null) {  return null;  }  if(root.val == val) {  return root;  }  TreeNode leftFind = find(root.left,val);  if(leftFind != null) {  return leftFind;  }  TreeNode rightFind = find(root.right,val);  if(rightFind != null) {  return rightFind;  }  return null;  
}//层序遍历:借助队列实现从上到下，从左到右  
public void levelOrder(TreeNode root) {  if(root == null) {  return ;  }  Queue<TreeNode> queue = new LinkedList<>();  queue.offer(root);//先押入一个结点  while(!queue.isEmpty())  {  TreeNode cur = queue.poll();  System.out.print(cur.val + " ");  if(cur.left != null) {  queue.offer(cur.left);  }  if(cur.right != null) {  queue.offer(cur.right);  }  }  System.out.println();  }// 判断一棵树是不是完全二叉树:借助队列实现  
public boolean isCompleteTree(TreeNode root) {  if(root == null) {  return true;  }  Queue<TreeNode> queue = new LinkedList<>();  queue.offer(root);  while(!queue.isEmpty()) {  TreeNode cur = queue.poll();  if(cur == null) {  break;  }  queue.offer(cur.left);  queue.offer(cur.right);  }  while(!queue.isEmpty()) {  TreeNode cur = queue.poll();  if(cur != null) {  return false;  }  }  return true;  
}

2.5 二叉树的模拟实现

import java.util.*;  //锻炼分治思想：将大问题化为相关的子问题  
public class BinaryTree {  static class TreeNode {  public char val;  public TreeNode left;  public TreeNode right;  public TreeNode(char val) {  this.val = val;  }  @Override  public String toString() {  return "TreeNode{" +  "val=" + val +  ", left=" + left +  ", right=" + right +  '}';  }  }  public TreeNode root;  //手动方式创造一棵树  public TreeNode creatTree() {  TreeNode node1 = new TreeNode('A');  TreeNode node2 = new TreeNode('B');  TreeNode node3 = new TreeNode('C');  TreeNode node4 = new TreeNode('D');  TreeNode node5 = new TreeNode('E');  TreeNode node6 = new TreeNode('F');  TreeNode node7 = new TreeNode('G');  TreeNode node8 = new TreeNode('H');  node1.left = node2;  node1.right = node3;  node2.left = node4;  node2.right = node5;  node3.left = node6;  node3.right = node7;  node5.right = node8;  this.root = node1;  return root;  }  // 前序遍历递归  public void preOrder(TreeNode root) {  //先访问根节点，再访问左子树，最后访问右子树  if(root == null) {  return ;//遇到空树返回  }  System.out.print(root.val + " ");  preOrder(root.left);  preOrder(root.right);  }  //非递归  public void preOrderNor(TreeNode root) {  if(root == null) {  return ;  }  //申请栈来保存当前’最近‘未访问完分支结点的父节点  Stack<TreeNode> stack = new Stack<>();  while(root != null || !stack.isEmpty()) {  while(root != null) {  stack.push(root);  System.out.print(root.val + " ");  root = root.left;  }  TreeNode cur = stack.pop();  root = cur.right;//压入右子树内容  }  System.out.println();  }  // 中序遍历递归  public void inOrder(TreeNode root) {  //先访问左子树，再访问根节点，最后访问右子树  if(root == null) {  return ;//遇到空树返回  }  inOrder(root.left);  System.out.print(root.val + " ");  inOrder(root.right);  }  //非递归  public void inOrderNor(TreeNode root) {  if(root == null) {  return ;  }  //申请栈来保存当前’最近‘未访问完分支结点的父节点  Stack<TreeNode> stack = new Stack<>();  while(root != null || !stack.isEmpty()) {  while(root != null) {  stack.push(root);  root = root.left;  }  TreeNode cur = stack.pop();  System.out.print(cur.val + " ");  root = cur.right;  }  System.out.println();  }  // 后序遍历递归  public void postOrder(TreeNode root) {  //先访问左子树，再访问右子树，最后访问根节点  if(root == null) {  return ;//遇到空树返回  }  postOrder(root.left);  postOrder(root.right);  System.out.print(root.val + " ");  }  //非递归  //难点：记录上一个打印过的值，避免重复打印  public void postOrderNor(TreeNode root) {  if(root == null) {  return ;  }  //申请栈来保存当前’最近‘未访问完分支结点的父节点  Stack<TreeNode> stack = new Stack<>();  TreeNode pre = null;//记录上一个打印的结点  while(root != null || !stack.isEmpty()) {  while(root != null) {  stack.push(root);  root = root.left;  }  TreeNode peekNode = stack.peek();//后序遍历不能直接pop，需要先peek  //右节点不存在时，或访问过时（peekNode.right == pre），直接打印当前结点  if(peekNode.right == null || peekNode.right == pre) {  System.out.print(stack.pop().val + " ");  pre = peekNode;//记录打印过结点  }else {  root = peekNode.right;//当右节点存在时，压入  }  }  System.out.println();  }  // 获取树中节点的个数:根节点+左子树节点数+右子树节点数  public int size(TreeNode root) {  if(root == null) {  return 0;  }  return size(root.left) + size(root.right) + 1;  }  // 获取叶子节点的个数:左子树叶子节点数 + 右子树叶子节点数  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);  }  // 获取第K层节点的个数:左子树第k-1层节点数+右子树第k-1层节点数  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);  }  // 获取二叉树的高度：左右子树最大高度 + 1（根节点）  public int getHeight(TreeNode root) {  if(root == null) {  return 0;  }  int leftHeight = getHeight(root.left);  int rightHeight = getHeight(root.right);  return Math.max(leftHeight,rightHeight) + 1;  }  // 检测值为value的元素是否存在:检查根节点，根节点不是再到左子树找，左子树找不到就到右子树找，都找不到就没有  public TreeNode find(TreeNode root, char val) {  if(root == null) {  return null;  }  if(root.val == val) {  return root;  }  TreeNode leftFind = find(root.left,val);  if(leftFind != null) {  return leftFind;  }  TreeNode rightFind = find(root.right,val);  if(rightFind != null) {  return rightFind;  }  return null;  }  //层序遍历:借助队列实现从上到下，从左到右  public void levelOrder(TreeNode root) {  if(root == null) {  return ;  }  Queue<TreeNode> queue = new LinkedList<>();  queue.offer(root);//先押入一个结点  while(!queue.isEmpty())  {  TreeNode cur = queue.poll();  System.out.print(cur.val + " ");  if(cur.left != null) {  queue.offer(cur.left);  }  if(cur.right != null) {  queue.offer(cur.right);  }  }  System.out.println();  }  // 判断一棵树是不是完全二叉树:借助队列实现  public boolean isCompleteTree(TreeNode root) {  if(root == null) {  return true;  }  Queue<TreeNode> queue = new LinkedList<>();  queue.offer(root);  while(!queue.isEmpty()) {  TreeNode cur = queue.poll();  if(cur == null) {  break;  }  queue.offer(cur.left);  queue.offer(cur.right);  }  while(!queue.isEmpty()) {  TreeNode cur = queue.poll();  if(cur != null) {  return false;  }  }  return true;  }  //翻转二叉树  public TreeNode invertTree(TreeNode root) {  if(root == null) {  return null;  }  if(root.left == null && root.right == null) {  return root;  }  TreeNode leftTmp = root.left;  TreeNode rightTmp = root.right;  root.left = invertTree(rightTmp);  root.right = invertTree(leftTmp);  return root;  }  //检查两棵树是否相同  public boolean isSameTree(TreeNode p, TreeNode q) {  if(p == q) {  return true;  }  //判断根节点相同不相同  if(p == null && q!= null || q == null && p!= 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);  }  //检查两棵树是否对称  public boolean isSymmetric(TreeNode root) {  if(root == null) {  return true;  }  //判断左子树和右子树是否对称  return _isSymmetric(root.right,root.left);  }  //判断两棵树是不是对称树  public boolean _isSymmetric(TreeNode p, TreeNode q) {  if(p == null && q!= null || q == null && p!= null) {  return false;  }  if(p == null && q == null) {  return true;  }  if(p.val != q.val) {  return false;  }  //递归实现判断  //一棵树的左子树（右子树）和另一棵树的右子树（左子树）是否对成  return _isSymmetric(p.left,q.right) && _isSymmetric(p.right,q.left);  }  //判断一棵树是否是另一棵树的子树:树中存在和子树一样的树就有子树  //分治  public boolean isSubtree(TreeNode root, TreeNode subRoot) {  if(root == null) {  return false;  }  if(isSameTree(root,subRoot)) {  return true;  }  //去左（右）子树中找是否存在和他相同的树，相同则存在子树  if(isSubtree(root.left,subRoot) || isSubtree(root.right,subRoot)) {  return true;  }  return false;  }  //判断一棵二叉树是否为平衡二叉树  //1 判断每个节点是否平衡  public boolean isBalanced1(TreeNode root) {  if(root == null) {  return true;  }  int leftHeight = getHeight(root.left);  int rightHeight = getHeight(root.right);  if(Math.abs(leftHeight - rightHeight) > 1) {  return false;  }  return isBalanced1(root.left) && isBalanced1(root.right);  }  //2 求结点高度时的返回值是否正常来判断  public boolean isBalanced(TreeNode root) {  if(root == null) {  return true;  }  return getHeight1(root) >= 0;  }  public int getHeight1(TreeNode root) {  if(root == null) {  return 0;  }  //高度结点返回值不正常代表不是平衡二叉树  int leftHeight = getHeight1(root.left);  if(leftHeight == -1) {  return -1;  }  int rightHeight = getHeight1(root.right);  if(rightHeight == -1) {  return -1;  }  if(Math.abs(leftHeight - rightHeight) > 1) {  return -1;  }  return Math.max(leftHeight,rightHeight) + 1;  }  //给定用’#‘表示null的字符串来创建和构造树  public static int i;//定义全局变量，避免形参值传递不改变实参的现象  public static TreeNode creatTree(String str) {  i=0;  TreeNode root = _creatTree(str);  return root;  }  public static TreeNode _creatTree(String str) {  char ch = str.charAt(i);  i++;  TreeNode root = null;  //'#'代表空，表示不用创建结点  if(ch != '#' && i < str.length()) {  root = new TreeNode(ch);//创建根节点  root.left = _creatTree(str);//创建左子树  root.right = _creatTree(str);//创建右子树  }  return root;  }  //中序后序还原二叉树:根据两排序结合：先建立根节点，再建立右子树，最后建立左子树  //中序：左 根节点 右  //后序：左 右 根节点  public TreeNode buildTreePost(char[] inorder, char[] postorder) {  postIndex = postorder.length - 1;  return _buildTreePost(inorder, 0, inorder.length - 1, postorder);  }  public static int postIndex;//定义全局变量不用传参，当把全局定量传参时依然存在局部优先  public TreeNode _buildTreePost(char[] inorder, int left, int right, char[] postorder) {  if(postIndex >= postorder.length || postIndex < 0 || left > right) {  return null;  }  TreeNode root = new TreeNode(postorder[postIndex--]);  int valIndex = findIndex(inorder,left,right,root.val);  root.right = _buildTreePost(inorder,valIndex + 1,right,postorder);  root.left = _buildTreePost(inorder,left,valIndex - 1,postorder);  return root;  }  //在范围内查找  public int findIndex(char[] inorder,int left,int right,int val) {  for(int i = left;i <= right;i++) {  if(inorder[i] == val) {  return i;  }  }  return -1;  }  //前序中序还原二叉树  public TreeNode buildTreePre(char[] preorder, char[] inorder) {  preIndex = 0;  return _buildTreePre(preorder,0,inorder.length - 1,inorder);  }  public static int preIndex;  public TreeNode _buildTreePre(char[] preorder, int left, int right, char[] inorder) {  if(left > right || preIndex >= preorder.length) {  return null;  }  TreeNode root = new TreeNode(preorder[preIndex++]);  int valIndex = findIndex(inorder,left,right,root.val);  root.left = _buildTreePre(preorder,left,valIndex-1,inorder);  root.right = _buildTreePre(preorder,valIndex+1,right,inorder);  return root;  }  //两个节点的最近公共祖先  public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {  if(root == null) {  return null;  }  //有一个结点==root，root就是最近公共祖先  if(p == root || q== root) {  return root;  }  //左右找最近共公祖先：都有则root是，否则则找到那边是  TreeNode leftRoot = lowestCommonAncestor(root.left,p,q);  TreeNode rightRoot = lowestCommonAncestor(root.right,p,q);  if(leftRoot != null && rightRoot != null) {  return root;  }else if(leftRoot != null) {  return leftRoot;  }else if(rightRoot != null) {  return rightRoot;  }  return null;  }  //层序遍历2：给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历  //（即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）  //借助队列来实现广度优先遍历，中间可以将每层结点的东西加入这一层的组合里  public List<List<Character>> levelOrderBottom(TreeNode root) {  List<List<Character>> list = new LinkedList<>();  if(root == null) {  return list;  }  Queue<TreeNode> queue = new ArrayDeque<>();  queue.offer(root);//先押入一个节点  while(!queue.isEmpty()) {  int size = queue.size();//先判断每一层有多少节点  List<Character> listCur = new LinkedList<>();//设置存储每层节点  //往listCur塞入每层结点的val，同时将下一层结点赛入queue  while(size != 0) {  TreeNode cur = queue.poll();  listCur.add(cur.val);  if(cur.left != null) {  queue.offer(cur.left);  }  if(cur.right != null) {  queue.offer(cur.right);  }  size--;  }  list.add(0,listCur);//头插使得插入顺序实现逆序  }  return list;  }  //层序遍历1：  public List<List<Character>> levelOrder1(TreeNode root) {  List<List<Character>> list = new LinkedList<>();  if(root == null) {  return list;  }  Queue<TreeNode> queue = new LinkedList<>();  queue.offer(root);  while(!queue.isEmpty()) {  int size = queue.size();  List<Character> listCur = new LinkedList<>();  while(size != 0) {  TreeNode cur = queue.poll();  listCur.add(cur.val);  if(cur.left != null) {  queue.offer(cur.left);  }  if(cur.right != null) {  queue.offer(cur.right);  }  size--;  }  list.add(listCur);  }  return list;  }  //根据二叉树创建字符串:关键点在于括号的额外判断  public String tree2str(TreeNode root) {  if(root == null) {  return "";  }  StringBuilder stringBuilder = new StringBuilder();  tree2str(root,stringBuilder);  return stringBuilder.toString();  }  public void tree2str(TreeNode root,StringBuilder stringBuilder) {  if(root == null) {  return ;  }  stringBuilder.append(root.val);  //递归创建结点，括号根据特定情况加  if(root.left != null) {  stringBuilder.append('(');  tree2str(root.left,stringBuilder);  stringBuilder.append(')');  }else if(root.right != null) {  //左边为空，右边不为空就加()  stringBuilder.append("()");  }  if(root.right != null) {  stringBuilder.append('(');  tree2str(root.right,stringBuilder);  stringBuilder.append(')');  }  }  }

需要特别注意的是以上模拟二叉树实现的过程中不单单只是实现了与二叉树基础操作相关的内容，同时加入了一些常见二叉树OJ题的实现；
以下OJ题均已实现在二叉树的模拟实现中，并配有相对应的注释：

1. 检查两棵树是否相同
2. 判断某棵树是否是另一棵树的子树
3. 翻转二叉树
4. 判断一棵二叉树是否是平衡二叉树
5. 对称二叉树的判断
6. 给定用’#‘表示null的先序遍历字符串来创建和构造树
7. 二叉树的层序遍历
8. 最近公共祖先
9. 根据一棵树的前序遍历与中序遍历构造二叉树
10. 根据一棵树的后序遍历与中序遍历构造二叉树
11. 二叉树创建字符串
12. 前序遍历的非递归
13. 中序遍历的非递归
14. 后序遍历的非递归