比如： 2.在具有2n个节点的完全二叉树中，叶子节点的个数是 （n ）个

对于奇数个节点假设为 N，N=n0+n2->N=2n0-1，

二叉树的存储

顺序存储和类似于链表的链式存储 ，二叉树的链式存储是通过一个一个的节点引用起来的，常见的表示方式有二叉（孩子表示法）和三叉（孩子双亲表示法）表示方式

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

二叉树的遍历

1.前序遍历（先根遍历）根->左子树->右子树

2.中序： 左 根 右

3.后序： 左 右 根

4.层序遍历

注意：

根据二叉树的某一个遍历是不能完全确定二叉树的。

如果只给前序和后序是不能创建二叉树的。

---

eg:

前序：ABDEHCFG；

中序：DBEHAFCG;

后序：DEHBFGCA; DHEBFGCA

基本操作： 

二叉树的前序遍历

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

递归的遍历思路及其子问题思路

class Solution {List list=new ArrayList<>();//因为你每一次递归都会new一个新的Listpublic List preorderTraversal(TreeNode root) {if(root==null){return list;}      list.add(root.val);preorderTraversal(root.left);preorderTraversal(root.right);return list;}
}

    List res = new ArrayList<>();// 判断非空if(null == root){return res;}// 使用双端队列Deque stack = new ArrayDeque<>();stack.add(root);while(!stack.isEmpty()){TreeNode node = stack.removeLast();res.add(node.val);// 要先加右孩子、再加左孩子if(null != node.right){stack.add(node.right);}if(null != node.left){stack.add(node.left);}}return res;        

获取节点个数 

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

叶子节点的个数 

 

  int getLeafNodeCount(Node root){if(root==null){return 0;}if(root.left==null&&root.right==null){//是叶子节点return 1;}return getLeafNodeCount(root.left)+getLeafNodeCount(root.right);}

获取第K层节点的个数

 int getKLevelNodeCount(Node root,int k){if(root==null||k<=0){//自己写的时候忘了这个了return 0;}if(k==1){return 1;}return getKLevelNodeCount(root.right,k-1)+getKLevelNodeCount(root.left,k-1);}

获取二叉树的高度

 int getHeight(Node root){if(root==null){return 0;}return Math.max(getHeight(root.left),getHeight(root.right))+1;//return root == null ? 0 : Math.max(getHeight(root.left),getHeight(root.right))+1;}

检测为value的值是否存在

先看根节点是不是要找的value，否则遍历整个二叉树。

    //先找根，然后左，然后右边找Node find(Node root,char val){if(root==null){return null;}if(root.val==val){return root;}Node ret = find(root.left,val);if(ret!=null){return ret;}ret=find(root.right,val);if(ret!=null){return ret;}return null;}

判断一棵树是否是完全二叉树

使用非递归的队列解决：

先把根节点放入队列，弹出栈顶元素放入cur；

当cur不为空的时候，放入cur的左右节点 ，若无放入null ......

当cur为空的时候，如果队列里面的值全是null，则是完全二叉树。 

    boolean isCompleteTree(Node root){if(root==null) return true;//空树就是完全二叉树；Queue queue=new LinkedList<>();queue.offer(root);while(!queue.isEmpty()){Node cur=queue.poll();if(cur!=null){queue.offer(root.left);queue.offer(root.right);}else{break;}}while(!queue.isEmpty()){Node top=queue.peek();if(top!=null){return false;}queue.poll();}return true;}

相同的树

节点的值相同，树的结构相同。

 //如果一个为空，一个不为空，结构不相同

 //p=null,q==null,pq是相同的树

 //p,q都不为空，但是p.val!=q.val,pq不是相同的树

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;}//p!=null&&q!=null&&p.val==q.valreturn isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);}
}

另一棵树的子树

 //先判断两棵树是不是相同的树；
 //如果不是。那麽分别判断 subRoot是不是root的左子树或者右子树；
 //是否相同？ 

class Solution {public boolean isSubtree(TreeNode root, TreeNode subRoot) {if(root==null||subRoot==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;}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;//p!=null&&q!=null&&p.val==q.valreturn isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);}
}

平衡二叉树

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

本题中，一棵高度平衡二叉树定义为：

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。

如果是平衡二叉树，那么他的每一个子树都是平衡二叉树

 //一个二叉树要是平衡二叉树，那么他的每一个子树都应该是平衡二叉树
 //root左树的高度-右树的高度<=1;
 //root的左树是平衡，右树也是

class Solution {//求高度的时间复杂度：O（N）；public int height(TreeNode root){if(root==null) return 0;return Math.max(height(root.left),height(root.right))+1;}//O(N^2)public boolean isBalanced(TreeNode root) {if(root==null) return true;int left=height(root.left);int right=height(root.right);return Math.abs(left-right)<=1&&isBalanced(root.left)&&isBalanced(root.right)?true:false;}
}

👀在我们递归去判断是否是平衡二叉树时，如果左树已经不平衡了，就没必要去判断右树，但是如何在获取高度的同时判断它是否为平衡二叉树？

class Solution {public int height(TreeNode root){if(root==null) return 0;int leftHeight=height(root.left);int rightHeight=height(root.right);if(leftHeight>=0 && rightHeight>=0 &&Math.abs(leftHeight-rightHeight)<=1){return Math.max(leftHeight,rightHeight)+1;}else{//说明不平衡return -1;}}public boolean isBalanced(TreeNode root) {if(root==null) return true;return height(root)>=0;}
}

 对称二叉树

判断是否是轴对称

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

二叉树的层序遍历

创建一个队列，放入元素，判断这个节点是否是空节点，如果不是空节点，就把它放入cur,并且打印，同时，把cur的左右节点依次放入队列中。 

class Solution {public List> levelOrder(TreeNode root) {           List> ret=new ArrayList<>();if(root==null) return ret;Queue queue=new LinkedList<>();queue.offer(root);while(!queue.isEmpty()){int size=queue.size();//代表当前层有多少节点List list = new ArrayList<>();while(size!=0){TreeNode cur=queue.poll();list.add(cur.val);if(cur.left!=null){queue.offer(cur.left);}if(cur.right!=null){queue.offer(cur.right);}size--;}ret.add(list);}return ret;}
}

普通写法（不内层分行打印，先写出下面这种，再写出正确答案）

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