剑指offer刷题总结(二)二叉树

1. 二叉搜索树第k个结点

题目描述：

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

代码实现：

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

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

    }

}
*/
public class Solution {
    private int count=0;
    private TreeNode treeNode;
    TreeNode KthNode(TreeNode pRoot, int k)
    {
        if(pRoot!=null){
            treeNode=KthNode(pRoot.left,k);
            count++;
            if(count==k){
                return pRoot;
            }else if(count>k){
                return treeNode;
            }else{
                treeNode=KthNode(pRoot.right,k);
                return treeNode;
            }
        }
        return null;
    }
}

2.从上往下打印二叉树

题目描述：

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

代码实现：

/**
 * @ClassName problem2
 * @Description TODO
 * @Author 倪然
 * @Date 2019/7/31 17:27
 * Version 1.0
 **/
 
 
/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

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

    }

}
*/
public class problem2 {
    /**
     * 1.根节点放到队列里面，队列不空，就打印队列头，打印这个节点，马上把这个节点的左右子节点放到队列中。
     * 2.再要访问一个节点，把这个节点的左右放入，此时队头是同层的，对位是打印出来的左右。依次先入先出就可以得到结果。
     * @param root
     * @return
     */
    public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
    
        ArrayList<Integer> arrayList=new ArrayList<>();
        LinkedList<TreeNode> linkedList=new LinkedList<>();

        if(root==null)
            return arrayList;
        linkedList.add(root);

        while(!linkedList.isEmpty()){
            TreeNode treeNode=linkedList.poll(); //取出队头节点
            arrayList.add(treeNode.val);
            if(treeNode.left!=null)
                linkedList.add(treeNode.left);   //将取出的节点的左孩子节点和右孩子节点加入队尾
            if(treeNode.right!=null)
                linkedList.add(treeNode.right);
        }

        return  arrayList;
    }
}

3. 二叉树打印成多行

题目描述：

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

题目思路：

• 开始时，last=节点1，nLast=null,把节点1放入队列queue,遍历开始，queue={1}。
• 从queue中弹出节点1并打印，然后把节点1的孩子依次放入queue,放入节点2时nlast节点2。放入节点3时，nlast=节点3此时发现弹出的节点1=last.所以换行，井令last=nlast=节点3, queue={2,3}。
• 从queue中弹出点2并打印，然后把节点2的孩子放入queue,放入节点4时nLast=节点4, queue={3,4}。

代码实现：

/**
 * @ClassName problem3
 * @Description 二叉树打印多行
 * @Author 倪然
 * @Date 2019/8/1 8:17
 * Version 1.0
 **/
public class problem3 {

    ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> resultlist=new ArrayList<>();
        if(pRoot==null)
            return resultlist;
        TreeNode last=pRoot;
        TreeNode nlast=null;
        Queue<TreeNode> queue=new LinkedList<>();
        queue.add(pRoot);
        ArrayList<Integer> arrayList=new ArrayList<>();
        while(!queue.isEmpty()){
            TreeNode treeNode=queue.poll();     //将队首节点取出
            arrayList.add(treeNode.val);

            if(treeNode.left!=null){       
                nlast=treeNode.left;           
                queue.add(treeNode.left);       //将左孩子加入队列
            }
            if(treeNode.right!=null){
                nlast=treeNode.right;           //更新nlast位置
                queue.add(treeNode.right);      //将右孩子加入队列
            }
            if(treeNode==last){
                resultlist.add(arrayList);      
                arrayList=new ArrayList<>();    //换行
                last=nlast;                     //更新last节点位置
            }
        }
        return resultlist;
    }
}

4. 按之字形顺序打印二叉树

题目描述：

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

思路：
利用两个栈的辅助空间分别存储奇数偶数层的节点，然后打印输出。或使用链表的辅助空间来实现，利用链表的反向迭实现逆序输出。

代码实现：

/**
 * @ClassName problem4
 * @Description 按之字形顺序打印二叉树
 * @Author 倪然
 * @Date 2019/8/1 9:35
 * Version 1.0
 **/
public class problem4 {
    public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> resultlist=new ArrayList<>();
        if(pRoot==null)
            return resultlist;

        Stack<TreeNode> stack1 = new Stack<>();     //奇数行栈
        Stack<TreeNode> stack2 = new Stack<>();     //偶数行栈
        stack1.add(pRoot);
        ArrayList<Integer> arrayList;

        stack1.add(pRoot);
        boolean isOdd=true;         //是否为奇数行

        while(!stack1.isEmpty()||!stack2.isEmpty()){
            arrayList=new ArrayList<>();
            if(isOdd){                  //如果为奇数行就将栈里的节点依次取出并将子孩子节点从左向右加入偶数栈
                while(!stack1.isEmpty()) {
                    TreeNode treeNode = stack1.pop();
                    if (treeNode.left != null)
                        stack2.push(treeNode.left);
                    if (treeNode.right != null)
                        stack2.push(treeNode.right);
                    arrayList.add(treeNode.val);
                }
            }
            else{                       //如果是偶数行就将栈里的节点依次取出并将子孩子节点从右向左加入奇数栈
                while (!stack2.isEmpty()){
                    TreeNode treeNode =stack2.pop();
                    if (treeNode.right != null)
                        stack1.push(treeNode.right);
                    if (treeNode.left != null)
                        stack1.push(treeNode.left);
                    arrayList.add(treeNode.val);
                }
            }
            isOdd=!isOdd;
            resultlist.add(arrayList);
        }
        return  resultlist;
    }
}

5. 二叉树中和为某一值的路径

题目描述：

输入一颗二叉树的跟节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前)

思路：

1. 首先将根节点放入链表，target减去这个根节点
2. 判断target是否为零同时是叶子节点，如果是就将当前的链表放在结果连表里
3. 如果不是，就递归去访问左右子节点。
4. 无论是找到没有，都要回退一步

代码实现：

/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
        this.val = val;
    }
}
*/


/**
 * @ClassName problem5
 * @Description 二叉树中和为某一值的路径
 * @Author niran
 * @Date 2019/8/1 10:23
 * Version 1.0
 **/
public class problem5 {
    ArrayList<ArrayList<Integer>> resultlist=new ArrayList<>();
    ArrayList<Integer> arrayList=new ArrayList<>();

    /**
     * 代码步骤：一个链表记录路径，一个存放这个链表的链表记录最终的结果。前序遍历去访问。先访问根，在递归在左右子树找。注意回退
     * 1.首先将根节点放入链表，target减去这个根节点
     * 2.判断target是否为零同时是叶子节点，如果是就将当前的链表放在结果连表里
     * 3.如果不是，就递归去访问左右子节点。
     * 4.无论是找到没有，都要回退一步
     * @param root
     * @param target
     * @return
     */
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int target) {

        if(root==null)
            return resultlist;
        target-=root.val;
        arrayList.add(root.val);
        if(target==0&&root.right==null&&root.left==null) {
            resultlist.add(new ArrayList<Integer>(arrayList));
        }
        else if(target>0){
            FindPath(root.left,target);
            FindPath(root.right,target);
        }
        arrayList.remove(arrayList.size()-1);
        return resultlist;
    }
}

6. 重建二叉树

题目描述：

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

思路：

由于在中序遍历序列中，有3个数字是左子树结点的值，因此左子树总共有3个左子结点。同样，在前序遍历的序列中，根结点后面的3个数字就是3个左子树结点的值，再后面的所有数字都是右子树结点的值。这样我们就在前序遍历和中序遍历两个序列中，分别找到了左右子树对应的子序列。

代码实现：

/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
 
    public TreeNode(int val) {
        this.val = val;
 
    }
 
}
*/

/**
 * @ClassName problem6
 * @Description 重建二叉树
 * @Author niran
 * @Date 2019/8/1 13:06
 * Version 1.0
 **/
public class problem6 {
    
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        TreeNode root=new TreeNode(pre[0]);
        int i;
        for(i=0;i<in.length;i++){      //找到中序遍历中根节点的位置
            if(in[i]==pre[0])
                break;
        }
        if(i!=0){
            int[] l_pre= Arrays.copyOfRange(pre,1,i+1); 
            int[] l_in=Arrays.copyOfRange(in,0,i);   //根节点左边的树是左子树中序遍历的结果
            root.left=reConstructBinaryTree(l_pre,l_in);
        }
        if(i!=in.length-1){
            int[] r_pre= Arrays.copyOfRange(pre,i+1,in.length);
            int[] r_in= Arrays.copyOfRange(in,i+1,in.length);  //根节点右边的数是右子树中序遍历的结果
            root.right=reConstructBinaryTree(r_pre,r_in);
        }
        return root;
    }
}

7. 树的子结构

题目描述:

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

思路：

• 先从根开始再把左作为根，再把右作为根由本函数决定。把一个为根的时候的具体比对过程是第二个函数决定。
• 从根可以认为是一颗树，从左子树开始又可以认为是另外一颗树，从右子树开始又是另外一棵树。
• 本函数就是判断这一整颗树包不包含树2，如果从根开始的不包含，就从左子树作为根节点开始判断，
• 再不包含从右子树作为根节点开始判断。
• 整体算法递归流程控制。

代码实现：

/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
 
    public TreeNode(int val) {
        this.val = val;
 
    }
 
}
*/


/**
 * @ClassName problem7
 * @Description TODO
 * @Author niran
 * @Date 2019/8/1 13:59
 * Version 1.0
 **/
public class problem7 {


    /**
     * 先从根开始再把左作为根，再把右作为根由本函数决定。把一个为根的时候的具体比对过程是第二个函数决定。
     * 从根可以认为是一颗树，从左子树开始又可以认为是另外一颗树，从右子树开始又是另外一棵树。
     * 本函数就是判断这一整颗树包不包含树2，如果从根开始的不包含，就从左子树作为根节点开始判断，
     * 再不包含从右子树作为根节点开始判断。
     * 是整体算法递归流程控制。
     * @param root1
     * @param root2
     * @return
     */
    public boolean HasSubtree(TreeNode root1,TreeNode root2) {
        if(root1==null||root2==null)
            return false;
        return NodeEqule(root1,root2)||HasSubtree(root1.left,root2)||HasSubtree(root1.right,root2);
    }

    private boolean NodeEqule(TreeNode root1,TreeNode root2){
        if(root1==null&&root2!=null)
            return false;
        if(root2==null)
            return true;
        if(root1.val==root2.val){
            return NodeEqule(root1.left,root2.left)&&NodeEqule(root1.right,root2.right);
        }
        return false;
    }
}

8. 二叉树的镜像

题目描述:

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

输入描述:

二叉树的镜像定义：源二叉树 
    	    8
    	   /  \
    	  6   10
    	 / \  / \
    	5  7 9 11
    	镜像二叉树
    	    8
    	   /  \
    	  10   6
    	 / \  / \
    	11 9 7  5

代码实现：

/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
 
    public TreeNode(int val) {
        this.val = val;
 
    }
 
}
*/


/**
 * @ClassName problem8
 * @Description TODO 二叉树的镜像
 * @Author niran
 * @Date 2019/8/1 15:06
 * Version 1.0
 **/
public class problem8 {

    /**
     * 算法步骤
     * 1.节点为空直接返回
     * 2.递归对这个节点的左子树进行求镜像。对这个节点的右子树求镜像。
     * 3.交换节点的左右子树
     * @param root
     */
    public void Mirror(TreeNode root) {
        if (root == null)
            return;
        Mirror(root.left);
        Mirror(root.right);
        TreeNode treeNode = root.left;
        root.left = root.right;
        root.right = treeNode;
    }
}

9. 二叉搜素树的后序遍历序列

题目描述:

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

代码实现：

/**
 * @ClassName problem9
 * @Description TODO 二叉搜素树的后序遍历序列 
 * @Author niran
 * @Date 2019/8/1 15:29
 * Version 1.0
 **/
public class problem9 {

    /**二叉搜索树的性质：
     * 所有左子树的节点小于根节点，所有右子树的节点值大于根节点的值。
     * 算法步骤：
     * 1.后序遍历的最后一个值为root，在前面的数组中找到第一个大于root值的位置。
     * 2.这个位置的前面是root的左子树，右边是右子树。然后左右子树分别进行这个递归操作。
     * 3.其中，如果右边子树中有比root值小的直接返回false
     * @param sequence
     * @return
     */
    public boolean VerifySquenceOfBST(int [] sequence) {
        if(sequence.length==0)
            return false;

        int rootVal=sequence[sequence.length-1];
        boolean isBST=true;

        int i;
        for(i=0;i<sequence.length-1;i++){
            if(sequence[i]>rootVal)
                break;
        }
        for(int j=i;j<sequence.length-1;j++){
            if(sequence[j]<rootVal)
                isBST=false;
        }
        if(isBST&&i>0)
            isBST=VerifySquenceOfBST(Arrays.copyOfRange(sequence,0,i));
        if(isBST&&i<sequence.length-1)
            isBST=VerifySquenceOfBST(Arrays.copyOfRange(sequence,i,sequence.length-1));
        return isBST;
    }
}

10. 二叉搜索树与双向链表

题目描述：

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。

思路：
定义一个头结点指针和尾节点指针
中序遍历的步骤，在递归的中间部分不是输出节点值，而是调整尾节点指针指向。

代码实现：

/**
 * @ClassName problem10
 * @Description TODO
 * @Author niran
 * @Date 2019/8/1 16:08
 * Version 1.0
 **/
public class problem10 {

    private TreeNode head;   //头结点指针
    private TreeNode pop;    //尾节点指针

    public TreeNode Convert(TreeNode pRootOfTree) {
        if (pRootOfTree == null)
            return null;
        Convert(pRootOfTree.left);
        if (head == null) {   //初始时为头结点和尾节点复制
            head = pRootOfTree;
            pop = pRootOfTree;
        } else {               //调整尾节点指针
            pop.right = pRootOfTree;
            pRootOfTree.left = pop;
            pop = pop.right;
        }
        Convert(pRootOfTree.right);
        return head;
    }
}

11. 二叉树的深度

题目描述:

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

代码实现：

/**
 * @ClassName problem11
 * @Description 二叉树的深度
 * @Author niran
 * @Date 2019/8/1 16:44
 * Version 1.0
 **/
public class problem11 {

    public int TreeDepth(TreeNode root) {
        if(root==null)
            return 0;
        return Math.max(TreeDepth(root.left)+1,TreeDepth(root.right)+1);
    }
}

12. 平衡二叉树

题目描述:

输入一棵二叉树，判断该二叉树是否是平衡二叉树

描述：如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。

代码实现：

/**
 * @ClassName problem12
 * @Description 平衡二叉树
 * @Author niran
 * @Date 2019/8/1 16:50
 * Version 1.0
 **/
public class problem12 {

    public boolean IsBalanced_Solution(TreeNode root) {
        if(root==null)
            return true;
        if(Math.abs(TreeDepth(root.left)-TreeDepth(root.right))>1)
            return false;
        return IsBalanced_Solution(root.left)&&IsBalanced_Solution(root.right);
    }

    private int TreeDepth(TreeNode root) {
        if(root==null)
            return 0;
        return Math.max(TreeDepth(root.left)+1,TreeDepth(root.right)+1);
    }
}

13. 二叉树的下一个节点

题目描述：

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

代码实现：

/*
public class TreeLinkNode {
    int val;
    TreeLinkNode left = null;
    TreeLinkNode right = null;
    TreeLinkNode next = null;
    TreeLinkNode(int val) {
        this.val = val;
    }
}
*/

/**
 * @ClassName problem13
 * @Description TODO 二叉树的下一个节点
 * @Author niran
 * @Date 2019/8/2 12:36
 * Version 1.0
 **/
public class problem13 {
    /**
     * 1.如果有右孩子，后继节点就是最左边的
     * 2.如果没有右孩子，判断是否是父节点的左孩子，是的话，返回，不是继续往上找
     * 3.找不到就是null
     * @param pNode
     * @return
     */
    public TreeLinkNode GetNext(TreeLinkNode pNode)
    {
        if(pNode.right!=null){
            pNode=pNode.right;
            // 如果此时pNode没有左子树，那么它就是下一个结点 ，就是最左边的了
            //如果有左子树，那就在左子树找最左边的
            while(pNode.left!=null){
                pNode=pNode.left;
            }
            return pNode;
        }

        while(pNode.next!=null){
            // 找到一个结点是该其父亲的左孩子  ,找到就是返回父节点作为后记
            if(pNode==pNode.next.left){
                return pNode.next;
            }

            //找不到这个左孩子的，就继续往上，next其实是parent
            pNode=pNode.next;
        }
        return null;
    }
}

14. 对称的二叉树

题目描述：

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

代码实现：

/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
        this.val = val;
    }
}
*/

/**
 * @ClassName problem14
 * @Description TODO
 * @Author niran
 * @Date 2019/8/2 13:16
 * Version 1.0
 **/
public class problem14 {
    /**
     * 利用递归进行判断，
     * 若左子树的左孩子等于右子树的右孩子且左子树的右孩子等于右子树的左孩子，
     * 并且左右子树节点的值相等，则是对称的。
     * @param pRoot
     * @return
     */
    boolean isSymmetrical(TreeNode pRoot)
    {
        return isSame(pRoot.left,pRoot.right);
    }

    boolean isSame(TreeNode left,TreeNode right) {
        boolean same = false;
        if (left == null && right == null) {
            return true;
        }else if(left==null||right==null){
            return false;
        }
        return left.val == right.val && isSame(left.left, right.right) && isSame(left.right, right.left);

    }
}

14. 序列化二叉树

题目描述:

请实现两个函数，分别用来序列化和反序列化二叉树

代码实现：

/**
 * @ClassName problem15
 * @Description TODO
 * @Author niran
 * @Date 2019/8/2 14:14
 * Version 1.0
 **/
public class problem15 {

    String Serialize(TreeNode root) {
        if(root==null)
            return "#!";
        String str=root.val+"!";
        str+=Serialize(root.left);
        str+=Serialize(root.right);
        return str;
    }
    TreeNode Deserialize(String str) {
        String [] values = str.split("!");
        Queue<String> queue = new LinkedList<String>();
        for (int i = 0; i < values.length; i++) {
            queue.offer(values[i]);
        }
        return reconPre(queue);
    }
    TreeNode reconPre(Queue<String> queue) {
        String value = queue.poll();
        if(value.equals("#"))
            return null;
        TreeNode head = new TreeNode(Integer.valueOf(value));
        head.left = reconPre(queue);
        head.right = reconPre(queue);
        return head;
    }
}