前言：
针对二叉树，因为涉及到递归，需要跟多的练习强化递归的思想，其中也包括需要画图理解一些想不通的问题来提升自己！
一下面这些题为例，一起来提升自己的逻辑思维能力！(可能其中一些题已经写过，但是希望能再写一遍有助于提高代码能力)
相同的树：
思路：
1、从根节点开始递归，当两棵树如果一直递归，按照前序遍历(跟，左，右)，如果一起能够递归到最后根节点为null了，那么就开始返回true。
2、如果递归的过程出现两个root对应的val值不相等时，不再进行递归开始返回false。
3、如果递归的过程中出现一个root为null另一个root不为null，那么也直接返回false，不再进行递归。
也就有如下几种情况：
大概有这四种情况，接下来就来想想代码该如何写？
只需要想清楚什么时候需要开始回归，回归的条件是什么，如果遇到上述的四种条件就要开始回归，如果没有遇到上述的四种条件就继续递归左子树和右子树！
public boolean isSameTree(TreeNode p, TreeNode q) {
if(p == null && q == null) {
return true;
}
if(p == null && q != null || p != null && q == null) {
return false;
}
if(p.val != q.val) {
return false;
}
return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
}最后拿到的左右子树的true和false需要&&，最后的结果返回给上一级！！
此时我们发现了一个问题：
当我返回了一个true但是这个代码还是很傻的去判断其他的左子树和右子树是true还是false，那么如果我拿到了一个false，那么我就不需要再次判断另一个子树再去返回&&,这样做有点傻，那么只需要在回归之后需要判断一下是不是false如果是直接返回false。不需要再判断另一颗子树的情况。
优化代码如下:
public boolean isSameTree(TreeNode p, TreeNode q) {
if(p == null && q == null) {
return true;
}
if(p == null && q != null || p != null && q == null) {
return false;
}
if(p.val != q.val) {
return false;
}
boolean leftIsSame = isSameTree(p.left,q.left);
//优化点
if(leftIsSame == false) {
return false;
}
boolean rightIsSame = isSameTree(p.right,q.right);
//优化点
if(rightIsSame == false) {
return false;
}
return rightIsSame && leftIsSame;
}另一棵树的子树：
思路：
1、首先遍历主树，找到root的val等于另一棵树的root的val。
2、之后就开始以找到的root为一棵树的root，开始判断两棵树是否相同，如果相同直接返回true，如果不相同那就继续遍历主树，直到遍历结束。
因为这里面有判断两个树是否相同，可以直接使用判断两个树是否相同的代码。
代码如下：
时间复杂度(O(m*n))
public boolean isSubtree(TreeNode root, TreeNode subRoot) {
if(root == null) {
return false;
}
boolean leftIsSame = isSubtree(root.left,subRoot);
if(leftIsSame) {
return true;
}
boolean rightIsSame = isSubtree(root.right,subRoot);
if(rightIsSame) {
return true;
}
if(root.val == subRoot.val) {
return isSameTree(root,subRoot);
}
return leftIsSame || rightIsSame;
}
public boolean isSameTree(TreeNode p, TreeNode q) {
if(p == null && q == null) {
return true;
}
if(p == null && q != null || p != null && q == null) {
return false;
}
if(p.val != q.val) {
return false;
}
boolean leftIsSame = isSameTree(p.left,q.left);
//优化点
if(leftIsSame == false) {
return false;
}
boolean rightIsSame = isSameTree(p.right,q.right);
//优化点
if(rightIsSame == false) {
return false;
}
return rightIsSame && leftIsSame;
}当然该代码是进行了一些简单的优化，虽然时间复杂度是没有发生改变，但是在运行上的执行时间变短了一些！！
翻转二叉树：
思路：
这一题比较简单，主要思路就是分别交换左子树和右子树，之后递归交换，最后直到root == null返回root。
......
后续的就不画了(太懒了)。
此时就有几种思想，
第一种常规思想，每次递归的时候就进行交换，最后直接返回即可。
第二种思想，就是在回归的时候进行交换!
希望这两种思想大家都可以掌握，对二叉树的理解会更进一层。
第一种代码：
public TreeNode invertTree(TreeNode root) {
if(root == null) {
return null;
}
if(root.right == null && root.left == null) {
return root;
}
//进行交换左右子树
TreeNode tmp = root.left;
root.left = root.right ;
root.right = tmp;
//交换结束，继续递归左右子树
invertTree(root.left);
invertTree(root.right);
return root;
}第二种代码：
public TreeNode invertTree(TreeNode root) {
if(root == null) {
return null;
}
if(root.right == null && root.left == null) {
return root;
}
invertTree(root.left);
invertTree(root.right);
TreeNode tmp = root.left;
root.left = root.right;
root.right = tmp;
return root;
}平衡二叉树：
思路：
这道题的大题的思路应该和上一题是一样的，以为就是递归每一个节点，再以每一个节点为root，去计算左右两边的深度，最后作差。
如果差值大于1，返回false，否则返回true。如果返回true需要继续递归，不能停止。
如果遇到false直接回归，不再递归下去，直到最后递归到root == null后返回！！
首先以这个思路写代码：
public boolean isBalanced(TreeNode root) {
if(root == null) {
return true;
}
if(Math.abs(height(root.left) - height(root.right)) > 1) {
return false;
}
return isBalanced(root.left) && isBalanced(root.right);
}
public int height(TreeNode root) {
if(root == null) {
return 0;
}
int leftHeight = height(root.left);
int rightHeight = height(root.right);
return Math.max(leftHeight,rightHeight) + 1;
}这个代码的时间复杂度是O(N^2).
那么可不可以将该代码的时间复杂度降至O(N)呢？
答案是可以的，接下来就来画图分析一下：
如果这样做，那么时间复杂度就可以降至O(N)。
代码如下：
public boolean isBalanced(TreeNode root) {
return height(root) != -1;
}
public int height(TreeNode root) {
if(root == null) {
return 0;
}
int leftHeight = height(root.left);
if(leftHeight == -1) {
return -1;
}
int rightHeight = height(root.right);
if(rightHeight == -1) {
return -1;
}
if(Math.abs(leftHeight - rightHeight) >1) {
return -1;
}else {
return Math.max(leftHeight,rightHeight) +1;
}
}二叉树遍历：
思路：
要求是遍历字符串，通过前序遍历构建二叉树，最后再通过中序遍历输出结构。
首先先序遍历就是先创建每一个节点，当遇到'#'时，开始回归，并连接每一个左右子树。
图示如下：
此时可以分析一下，当遍历遇到'#'就返回。
代码如下：
class TreeNode {
char val;
public TreeNode left;
public TreeNode right;
public TreeNode(char val) {
this.val = val;
}
}
private int i;
public TreeNode creatTree(String str) {
if(str.charAt(i) == '#') {
i++;
return null;
}
TreeNode root = new TreeNode(str.charAt(i));
i++;
root.left = creatTree(str);
root.right = creatTree(str);
return root;
}
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 处理多个 case
String str = in.nextLine();
Main m = new Main();
TreeNode root = m.creatTree(str);
m.inOrder(root);
m.i = 0;
}
}这一个非常简单，大家可以尝试一下。
二叉树的分层遍历：
思路：
这里需要借助队列实现二叉树的分层遍历。
当二叉树的root不为空的时候就放入队列中，之后将root出队列，放入顺序表中，之后需要判断一下出队列的左子树是否为空，如果不为空，将左子树放入队列中，右子树是否为空，如果右子树也不为空，将右子树也放入队列中。
直到最后队列为空时结束遍历！！
如图所示：
第一步：
第二步，出队列，并且判断左右子树是否为空，如果不为空需要入队！
第三步：以此类推
最后：
这道题有一个难点，在于如何保证每一层数据和二叉树对应，也就是应该输出[ [ 1 ] , [ 2 , 3 ] , [4]]
这里需要用到队列中的size() ,也就是每次入队之后需要记录一个size(),最后按size()次出队！
代码如下：
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> list = new ArrayList<>();
if(root == null) {
return list;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()) {
List<Integer> l1 = new ArrayList<>();
int ret = queue.size();
while(ret != 0) {
TreeNode tmp = queue.poll();
l1.add(tmp.val);
if(tmp.left != null) {
queue.offer(tmp.left);
}
if(tmp.right != null) {
queue.offer(tmp.right);
}
ret--;
}
list.add(l1);
}
return list;
}二叉树的最近公共最近祖先：
236. 二叉树的最近公共祖先 - 力扣（LeetCode）
思路：
要找到最近公共祖先那么就有以下三种情况：
1、当p/q等于root时，此时最近公共祖先直接返回root。
2、当p/q位于root的两侧时，此时如果在一侧找到了p/q,另一侧找到了q/p，那么也直接返回root。
3、当p和q位于root的同一侧时，此时需要遍历二叉树。
如图上述的三种情况。
代码如下：
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null) {
return null;
}
if(p == root || q == root) {
return root;
}
if(root.left == p && root.right == q || root.left == q && root.right == p) {
return root;
}
TreeNode leftNode = lowestCommonAncestor(root.left,p,q);
TreeNode rightNode = lowestCommonAncestor(root.right,p,q);
if(leftNode != null && rightNode != null) {
return root;
}
if(leftNode != null && rightNode == null) {
return leftNode;
}else {
return rightNode;
}
}思路2：
刚刚这个思路是大多数人可以想到的方法，但是此时还有另外一种思想，也就是我只需要找到p和q从根节点出发的两条路径，之后再去求两个路劲的第一个公共交点，最后该交点就是所要找的最近公共祖先。
此时需要借助栈去实现，将路线存在栈当中。
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
Stack<TreeNode> st1 = new Stack<>();
Stack<TreeNode> st2 = new Stack<>();
TreeNode root1 = findRoute(root,p,st1);
TreeNode root2 = findRoute(root,q,st2);
int num = st1.size() - st2.size();
while(num>0) {
st1.pop();
num--;
}
while(num<0) {
st2.pop();
num++;
}
TreeNode c = findCommenRoute(st1,st2);
return c;
}
public TreeNode findCommenRoute(Stack<TreeNode> st1,Stack<TreeNode> st2) {
while(st1.size() != 0) {
if(st1.peek() == st2.peek()) {
return st1.peek();
}else {
st1.pop();
st2.pop();
}
}
return null;
}
public TreeNode findRoute(TreeNode root,TreeNode node,Stack<TreeNode> st) {
if(root == null) {
return null;
}
st.push(root);
TreeNode leftFind = findRoute(root.left,node,st);
if(leftFind == node) {
return leftFind;
}else if(leftFind != null){
st.pop();
}
TreeNode rightFind = findRoute(root.right,node,st);
if(rightFind == node) {
return rightFind;
}else if(rightFind != null){
st.pop();
}
return root;
}从前序与中序遍历序列构造二叉树：
105. 从前序与中序遍历序列构造二叉树 - 力扣（LeetCode）
思路：
在做这道题之前，首先要弄懂如果不写代码，能不能给一个前序和中序遍历还原二叉树？
先拿这一个举例：
前序：[3,9,20,15,7]
中序：[9,3,15,20,7]
前序和后续都是相当于告诉我们根节点的位置。中序告诉我们左子树和右子树。
有人问这数是怎么来的，是凭感觉拼出来的吗？
答案肯定不是，
首先在前序遍历当中找到第一个根节点，接着在中序遍历中找到对应的根节点，之后将中序遍历的数组分成两部分，左边一部分就是左子树，右边一部分就是右子树，紧接着，继续遍历前序遍历，找到第二个根节点，之后在刚刚分解之后的左子树中找到对应的根节点，如果左子树的最后一个元素找完了，或者就没有左子树，紧接着在最开始的右子树中用同样的方法去找。
如图所示：
步骤画的非常清楚，大家可以参考一下。
那么反映到代码中，应该怎么写呢？
首先做的就是用i遍历前序遍历的数组，之后在中序遍历中找到对应的位置紧接着将该数组分成左右两部分，之后再++i，在中序遍用同样的方法遍历左边部分，最后回归，再遍历右半部分。每次都创建一个节点，等到回归的时候及那个节点连起来。
代码如下：
public int i;
public TreeNode buildTree(int[] preorder, int[] inorder) {
return buildTreeChild(preorder,inorder,0,preorder.length-1);
}
public TreeNode buildTreeChild(int [] preorder,int[] inorder,int ibegin,int iend) {
if(ibegin > iend) {
return null;
}
TreeNode root = new TreeNode(preorder[i]);
int n = findChild(inorder,ibegin,iend,preorder[i]);
i++;
root.left = buildTreeChild(preorder,inorder,ibegin,n-1);
root.right = buildTreeChild(preorder,inorder,n+1,iend);
return root;
}
public int findChild(int[] inorder,int ibegin,int iend,int k) {
for(int j = ibegin ; j<=iend ; j++) {
if(inorder[j] == k) {
return j;
}
}
return -1;
}从中序与后序遍历序列构造二叉树：
106. 从中序与后序遍历序列构造二叉树 - 力扣（LeetCode）
思路：
该题的思路和上一题是有点相似的，首先大体思路就是先找根节点，之后是右子树，最后再左子树，后续遍历序列中中找到根节点(从后往前找)，之后再是右子树，再是左子树。
返回的条件就是ibegin>iend,和尚议题是一样的！！
代码如下：
public int i;
public TreeNode buildTree(int[] inorder, int[] postorder) {
i = postorder.length-1;
return buildTreeChild(inorder,postorder,0,inorder.length-1);
}
public TreeNode buildTreeChild(int[] inorder,int[] postorder,int ibegin,int iend) {
if(ibegin > iend) {
return null;
}
TreeNode root = new TreeNode(postorder[i]);
int n = findChild(inorder,ibegin,iend,postorder[i]);
i--;
root.right = buildTreeChild(inorder,postorder,n+1,iend);
root.left = buildTreeChild(inorder,postorder,ibegin,n-1);
return root;
}
public int findChild(int[] inorder,int ibegin,int iend,int k) {
for(int j = ibegin ; j<=iend ; j++) {
if(inorder[j] == k) {
return j;
}
}
return -1;
}根据二叉树创建字符串：
606. 根据二叉树创建字符串 - 力扣（LeetCode）
思路：
首先我们在这里需要使用StringBuild类或者StringBuffer类，因为这两个类型中的字符串是可以改变的，在不创建新的字符串的条件下。
那么就该熟悉一下这一张表：
有关这两个类的使用，可以自己查阅。
有以下几种可能：
1、二叉树是一棵完全二叉树，也就是有右子树一定会存在左子树，此时我们不需要返回"()"。
2、二叉树不是一棵完全二叉树，也就是有右子树，但是没有左子树，此时，在我们递归完最后的左子树的时候回归时需要append("()")。
3、前序遍历先遍历左子树，后遍历右子树。
代码如下：
StringBuffer s;
public String tree2str(TreeNode root) {
s = new StringBuffer();
treestr1(root,s);
return s.toString();
}
public TreeNode treestr1(TreeNode root,StringBuffer s) {
if(root == null) {
return null;
}
s.append(root.val);
if(root.left != null) {
s.append("(");
treestr1(root.left,s);
s.append(")");
}else {
if(root.right != null) {
s.append("()");
}else {
return null;
}
}
if(root.right != null) {
s.append("(");
treestr1(root.right,s);
s.append(")");
}else {
return null;
}
return root;
}二叉树前序遍历非递归实现：
思路：
还是前序遍历，只不过这时候换一种思想去做，用非递归的方式解决。
也就是需要一个栈和一个顺序表去存储元素。
顺序表中的内容就是最后的结果，栈可以先进后出，保证了在遍历完左子树的时候还能回去找到右子树遍历！
具体做法如图所示：
......
综上总结就是：
当我拿到一个root如果root.left等于null，那么我就将拿到的元素pop()出来将其赋值给root，然后去判断root.right是否等于null，如果也等于空那就继续pop()。
代码如下：
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
Stack<TreeNode> s = new Stack<>();
if(root == null) {
return list;
}
TreeNode node = root;
while(!s.isEmpty() || node != null) {
while(node != null) {
list.add(node.val);
s.push(node);
node = node.left;
}
node = s.pop();
node = node.right;
}
return list;
}