//java
   public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        /*根据前序遍历和中序遍历确定一棵二叉树*/
        //递归实现
        if(pre==null||in==null||pre.length==0)
            return null;
        return reConstructBinaryTree(pre,in,0,pre.length-1,0,in.length-1);
    }
    public TreeNode reConstructBinaryTree(int [] pre,int [] in,int pre_begin,
                                          int pre_end,int in_begin,int in_end)
    {
        ////前序序列：从pre_begin到pre_end,  中序序列：从in_begin到in_end
        //递归结束条件
        if(pre_begin>pre_end || in_begin>in_end)
            return null;
        
        int rootValue=pre[pre_begin];
        TreeNode root=new TreeNode(rootValue);  //第一个节点就是根节点
        if(pre_begin==pre_end || in_begin==in_end)
            return root;
        //在中序序列中，找到root，前面的就是左子树，右边的就是右子树
        int rootIn=in_begin; //root在中序序列中的位置
        while(rootIn<=in_end && in[rootIn]!=rootValue)
            rootIn++;
        
        int left_count=rootIn-in_begin; //左子树节点个数							      	
   		root.left=reConstructBinaryTree(pre,in,pre_begin+1,pre_begin+left_count,
                                   in_begin,rootIn-1);
      	root.right=reConstructBinaryTree(pre,in,pre_begin+left_count+1,
                                       pre_end,rootIn+1,in_end);
        return root;
    }

17、树的子结构

　　题目描述：

输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

　　解题思路：递归

　　注意问题：

　　补充知识点：

//java
   public boolean HasSubtree(TreeNode root1,TreeNode root2) {
        if(root1==null || root2==null)
            return false;
        boolean res=false;
        if(root1.val==root2.val) //有相同的根节点，判断第二步
            res=doesTree1HasTree2(root1,root2);
        if(!res) //不满足，继续在子树中查找
            res=HasSubtree(root1.left,root2); //左子树
        if(!res) //左子树也没有找到，右子树查找
            res=HasSubtree(root1.right,root2); //右子树
        return res;
    }
    //以R为根的子树是否包含和树B相同的结构
    public boolean doesTree1HasTree2(TreeNode root1,TreeNode root2){ 
        if(root2==null)
            return true;
        if(root1==null)
            return false;
        if(root1.val!=root2.val)
            return false;
        return doesTree1HasTree2(root1.left,root2.left) && doesTree1HasTree2(root1.right,root2.right);
    }

18、二叉树的镜像

　　题目描述：

操作给定的二叉树，将其变换为原二叉树的镜像。

——树和二叉树（共15道题目）/18.png)

　　解题思路：递归

　　注意问题：

　　1.中序遍历不行，先序遍历和后序遍历可以；

　　2.提倡使用先序遍历；

　　补充知识点：

//java
    public void Mirror(TreeNode root) {
        /*思路：左右结点互换*/
        if(root!=null){
            if(root.left!=null || root.right!=null){
                TreeNode temp=root.left;
                root.left=root.right;
                root.right=temp;
                Mirror(root.left);
                Mirror(root.right);
            }
        }
    }

22、从上往下打印二叉树

　　题目描述：

从上往下打印出二叉树的每个节点，同层节点从左至右打印。

　　解题思路：二叉树的层次遍历：队列；

　　注意问题：

　　1.要导入：import java.util.LinkedList; import java.util.Queue;否则编译通不过；

　　2.左右子节点入队列之前要判空；

　　3.queue.size()返回值是整数；并且不可以用queue!=null来判断；仔细理解队列为空和队列元素为零的区别：前者是指针为空；

　　补充知识点：

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
        ArrayList<Integer> res=new ArrayList();
        if (root==null)
            return res;
        Queue<TreeNode> queue=new LinkedList<>();
        queue.add(root);
        while(queue.size()!=0)
        {
            TreeNode temp=queue.poll();
            res.add(temp.val);
            if(temp.left!=null)
                queue.add(temp.left);
            if(temp.right!=null)
                queue.add(temp.right);
        }
        return res;
    }
}

23、二叉搜索树的后序遍历序列

　　题目描述：

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。

　　解题思路：最后一个节点肯定时根，前面的序列中，比根小的是左子树，比分大的是右子树，找到左右子树的分界点，左子树递归判断；右子树中出现比根节点小的数则返回false，否则同左子树一样，递归判断，当左子树和右子树同时成立时，整棵树就是；

　　注意问题：

　　1.终止条件：end<=begin;

　　2.找左右子树的分界点时：用for循环，如果循环里已经有i++了，那么条件里面就不要写I++了，否则i++执行两次；

　　3.一层递归有true和false两个出口，不要忽略false的出口；

　　补充知识点：

public class Solution {
    public boolean VerifySquenceOfBST(int [] sequence) {
        if (sequence==null || sequence.length==0)
            return false;
        return VerifySquence0fBST(sequence,0,sequence.length-1);
    }
    public boolean VerifySquence0fBST(int [] a,int begin,int end)
    {
        if (end<=begin)
            return true;
        int i;
        for (i=begin;i<end;)
        {
            if (a[i]<a[end])
                i++;
            else
                break;
        }
        int j;
        for(j=i;j<end;j++)
            if (a[j]<a[end])
                return false;
        boolean left=VerifySquence0fBST(a,begin,i-1);
        boolean right=VerifySquence0fBST(a,i,end-1);
        return left && right;
    }
}

38、二叉树的深度

　　题目描述：

输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。

　　解题思路：递归

　　注意问题：递归结束条件判断；

　　补充知识点：

//java
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;
    }
}
public class Solution {
    public int TreeDepth(TreeNode root) {
        if(root==null)
            return 0;
        int leftDepth=TreeDepth(root.left);
        int rightDepth=TreeDepth(root.right);
        int depth=leftDepth>rightDepth?leftDepth:rightDepth;
        return 1+depth;
    }
}

39、平衡二叉树

　　题目描述：

输入一棵二叉树，判断该二叉树是否是平衡二叉树。这里的定义是：如果某二叉树中任意结点的左、右子树的深度相差不超过1，那么它就是一棵平衡二叉树。

　　解题思路：后序遍历：先判断左子树是否平衡，再判断右子树是否平衡，当左右子树均平衡时，再判断根是否平衡。

　　注意问题：

　　1.在求树的深度的算法的基础上，增加平衡的判断：求出左子树深度之后，要及时判断是否平衡；求出右子树之后，也要及时判断是否平衡；（如果不判断，只判断整棵树是否平衡，当二叉树为左子树单支链时，其左子树深度为-1，右子树深度为0，则|-1-0|=1不大于1，即该二叉树是平衡二叉树，与事实相反）在返回整棵树的深度之前，也要进行平衡的判断；

　　补充知识点：

//java
public class Solution {
    public boolean IsBalanced_Solution(TreeNode root) {
        if (root==null)
            return true;
        int res=getDepth(root);
        if (res==-1)
            return false;
        return true;
    }
    public int getDepth(TreeNode root)
    {
        if (root==null)
            return  0;
        int left=getDepth(root.left);
        if (left==-1)
            return -1;
        int right=getDepth(root.right);
        if (right==-1)
            return -1;
        if (Math.abs(left-right)>1)
            return -1;
        return left>right?left+1:right+1;


    }
}

57、二叉树的下一个结点

　　题目描述：

给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。

　　解题思路：

找一个结点在中序遍历序列中的下一个结点共有三种不同的情况：

如果一个结点有右子树，那么它的下一个结点就是它的右子树中最左边的那个结点，也就是说，从它的右子结点出发一直访问左指针，最后就可以找到这个最左结点。
如果一个结点没有右子树，那么需要再进一步考虑，不难知道：如果这个结点是其父结点的左结点，那么根据中序遍历规则，它的下一个结点就是它的父结点。
第三种情况略复杂一些，当一个结点既没有右子树，也不是其父结点的左结点时，我们可以沿着指向父结点的指针一直向上遍历，直到找到一个是它自身的父结点的左孩子的结点，如果这样的结点存在，那么这个结点的父结点就是我们要找的下一个结点。

　　注意问题：

　　补充知识点：

//java
public class TreeLinkNode {
    int val;
    TreeLinkNode left = null;
    TreeLinkNode right = null;
    TreeLinkNode next = null;

    TreeLinkNode(int val) {
        this.val = val;
    }
}
public class Solution {
    public TreeLinkNode GetNext(TreeLinkNode pNode){
        /*
        思路：三种情况：（1）若给定结点有右子树，则下一个结点是它右子树中最左边的结点
            （2）若该结点没有右子树，并且是父节点的左结点，则下一个结点就是他的父节点
            （3）若该结点没有右子树，并且是父节点的右结点，则应该沿着父节点向上，直到找到的结点是一个左结点。则下一个结点是该左结点的父节点
        */
        if(pNode==null)
            return null;
        TreeLinkNode res=null;
        if(pNode.right!=null){ //有右子树
            res=pNode.right;
            while(res.left!=null)
                res=res.left;
        }else{  //没有右子树
            TreeLinkNode parent=pNode.next; //父节点
            if(parent!=null && pNode==parent.left) //是父节点的左结点
                res=parent;
            else{ //是父节点的右结点
                while(parent!=null && parent.next!=null && parent!=parent.next.left)
                    parent=parent.next;
                res=parent==null? null : parent.next;
            } 
        }
        return res;
    }
}

58、对称的二叉树

　　题目描述：

请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。

　　解题思路：有相当的技巧性：对称二叉树的规律：根结点的左右子树相同，左子树的左子树和右子树的右子树相同，左子树的右子树和右子树的左子树相同即可。

　　注意问题：

　　补充知识点：

//java
//解法一：递归法，时间复杂度O(n),空间复杂度O(n)
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;
    }
}
public class Solution {
    boolean isSymmetrical(TreeNode pRoot){
        //左的左，和右的右进行比较，左的右和右的左比较
        if(pRoot==null)
            return true;
        return isSymmetrical(pRoot.left,pRoot.right);
    }
    boolean isSymmetrical(TreeNode pleft,TreeNode pright){
        if(pleft==null && pright==null)
            return true;
        if(pleft==null || pright==null)
            return false;
        if(pleft.val!=pright.val)
            return false;
        return isSymmetrical(pleft.left,pright.right) && isSymmetrical(pleft.right,pright.left);
    }
}

59、按之字形顺序打印二叉树

　　题目描述：

请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。

　　解题思路：

　　注意问题：

　　补充知识点：

//java

60、把二叉树打印成多行

　　题目描述：

从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。

　　解题思路：

　　注意问题：

　　补充知识点：

//java

62、二叉搜索树的第k个结点

　　题目描述：

给定一棵二叉搜索树，请找出其中的第k小的结点。例如（5，3，7，2，4，6，8）中，按结点数值大小顺序第三小结点的值为4。

　　解题思路：二叉搜索树的特点：左结点的值<根结点的值<右结点的值。因此，我们不难得到如下结论：如果按照中序遍历的顺序对一棵二叉搜索树进行遍历，那么得到的遍历序列就是递增排序的。设置两个全局变量，num和res，中序遍历，当num==1时，用res把当前节点记录下来。

　　注意问题：

　　1.if(num==1){res=pRoot;num--;}这一段代码，如果没有num—，则当num==1之后，条件永远成立，起不到只执行一次的作用；

　　2.递归前中后序遍历的时候，要先判空；

　　补充知识点：二叉搜索树

//java
class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
public class Solution {
    int num;
    TreeNode res;
    TreeNode KthNode(TreeNode pRoot, int k)
    {
        if (pRoot==null || k<1)
            return null;
        num=k;
        findKthNode(pRoot);
        return res;
    }
    void findKthNode(TreeNode pRoot)
    {
        if (pRoot==null)
            return;
        findKthNode(pRoot.left);
        if(num==1)
        {
            res=pRoot;
            num--;
        }
        else
            num--;
        findKthNode(pRoot.right);
    }
}

补充：

前序、中序、后续遍历递归算法：

typedef struct TreeNode
{
    int data;
    TreeNode * left;
    TreeNode * right;
    TreeNode * parent;
}TreeNode;
 
void pre_order(TreeNode * Node)//前序遍历递归算法
{
    if(Node == NULL)
        return;
    printf("%d ", Node->data);//显示节点数据，可以更改为其他操作。在前面
    pre_order(Node->left);
    pre_order(Node->right);
}
void middle_order(TreeNode *Node)//中序遍历递归算法
{
    if(Node == NULL)
        return;
    middle_order(Node->left);
    printf("%d ", Node->data);//在中间
    middle_order(Node->right);
}
void post_order(TreeNode *Node)//后序遍历递归算法
{
    if(Node == NULL)
        return; 
    post_order(Node->left);
    post_order(Node->right);
    printf("%d ", Node->data);//在最后
}

不忘初心

剑指offer(4)——树和二叉树（共15道题目）

树和二叉树（共15道题目）

补充：