剑指offer第二版-37.序列化二叉树

本系列导航:剑指offerjava实现导航帖

面试题7:重建二叉树

面试题37:序列化二叉树

题目:

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

       1
      /  
    2     3
   /     / 
  4      5  6
           /
    7      8

题目要求:实现两个函数,分别用来序列化和反序列化二叉树。

思路:

前序遍历的第一个数字就是根节点的值,扫描中序遍历序列,就能确定根节点的值。根据终须遍历的特点,在根节点的值前面的数字都是左子树的值,位于根节点后面的值都是右子树的节点的值。

解题思路:此题能让人想到重建二叉树。但二叉树序列化为前序遍历序列和中序遍历序列,然后反序列化为二叉树的思路在本题有两个关键缺点:1.全部数据都读取完才能进行反序列化。2.该方法需要保证树中节点的值各不相同。其实,在遍历结果中,记录null指针后(比如用一个特殊字符$),那么任何一种遍历方式都能回推出原二叉树。但是如果期望边读取序列化数据,边反序列化二叉树,那么仅可以使用前序或层序遍历。但层序记录的null个数要远多于前序,因此选择使用记录null指针的前序遍历进行序列化。

代码实现:

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */
 /******
  * 前序遍历的第一个数便是根节点,在中序遍历的数组中找到根节点位置,便可以分别找到左子树
  * 和右子树的数目和位置,再分别递归左右子树,得到根节点的左右子节点
  **/
public class Solution {
    /**
     *@param preorder : A list of integers that preorder traversal of a tree
     *@param inorder : A list of integers that inorder traversal of a tree
     *@return : Root of a tree
     */

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder.length != inorder.length ) {
            return null;
        }
        return myBuildTree(preorder, 0, preorder.length-1, inorder, 0, inorder.length-1);
    }
    private TreeNode myBuildTree(int[] preorder, int prestart, int preend,
                                 int[] inorder, int instart, int inend) {
        //
        if (instart > inend || prestart > preend) {
            return null;
        }

        TreeNode root = new TreeNode(preorder[prestart]);
        int pos = findPos(inorder, instart, inend, preorder[prestart]);
        root.left = myBuildTree(preorder, prestart+1,prestart+pos-instart,
                                inorder,instart, pos-1);
        root.right = myBuildTree(preorder, prestart+pos-instart+1,preend,
                                 inorder, pos+1, inend);
        return root;
    }
    private int findPos(int[] nums,int start, int end, int target) {
        int pos = 0;
        for(int i = start; i <= end; i++) {
            if (nums[i] == target) {
                pos = i;
            }
        }
        return pos;
    }
}

面试题8:二叉树的下一个节点

package chapter4;import structure.TreeNode;/** * Created by ryder on 2017/7/19. * 序列化二叉树 */public class P194_SerializeBinaryTrees { public static String serialize(TreeNode<Integer> root){ if(root==null) return "$,"; StringBuilder result = new StringBuilder(); result.append; result.append; result.append(serialize(root.left)); result.append(serialize(root.right)); return result.toString(); } public static TreeNode<Integer> deserialize(String str){ StringBuilder stringBuilder = new StringBuilder; return deserializeCore(stringBuilder); } public static TreeNode<Integer> deserializeCore(StringBuilder stringBuilder){ if(stringBuilder.length return null; String num = stringBuilder.substring(0,stringBuilder.indexOf; stringBuilder.delete(0,stringBuilder.indexOf; stringBuilder.deleteCharAt; if(num.equals return null; TreeNode<Integer> node = new TreeNode<>(Integer.parseInt; node.left = deserializeCore(stringBuilder); node.right = deserializeCore(stringBuilder); return node; } public static void main(String[] args){ // 1 // /  // 2 3 // / /  // 4 5 6 // 1,2,4,$,$,$,3,5,$,$,6,$,$ TreeNode<Integer> root = new TreeNode<Integer>; root.left = new TreeNode<Integer>; root.right = new TreeNode<Integer>; root.left.left = new TreeNode<Integer>; root.right.left = new TreeNode<Integer>; root.right.right = new TreeNode<Integer>; System.out.println("原始树:"+root); String result = serialize; System.out.println("序列化结果:"+result); TreeNode<Integer> deserializeRoot = deserialize; System.out.println("反序列后的树:"+deserializeRoot); }}

题目:

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

运行结果

思路:

此题包含三步:

  1. 如果此节点有右子树,下一个节点为右子节点的最左边的节点。
  2. 如果此节点没有右子树,并且如果此节点是其父节点的左子节点,则下一个节点为父节点。
  3. 如果此节点没有右子树,并且如果此节点是其父节点的右子节点,则一直向上找,直到找到第一个是其父节点左节点的节点,下一个节点就为此节点。
原始树:[1,2,3,4,5,6]序列化结果:1,2,4,$,$,$,3,5,$,$,6,$,$,反序列后的树:[1,2,3,4,5,6]

代码实现 :

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */
public class Solution {
    /**
     * @param T1, T2: The roots of binary tree.
     * @return: True if T2 is a subtree of T1, or false.
     */
    public boolean isSubtree(TreeNode T1, TreeNode T2) {
        //先判断T2,再判断T1
        if (T2 == null) {
        return true;    
    }
        if (T1 == null) {
        return false;
    }
    //从根节点出发判断,就相当于判断二者是否相等
    if (isEqual(T1, T2)) {
        return true;
    }
    if (isSubtree(T1.left, T2) || isSubtree(T1.right, T2)) {
        return true;
    }
    return false;
    }
    private boolean isEqual(TreeNode n1, TreeNode n2) {
        if (n1 == null || n2 == null) {
            return n1 == n2;
        }
        if (n1.val != n2.val) {
            return false;
        }
        return isEqual(n1.left, n2.left) && isEqual(n1.right, n2.right);
    }
}

面试26:树的子结构

题目:

输入两颗二叉树A和B,判断B是不是A的子结构

样例:

下面的例子中 T2 是 T1 的子树:

       1                3
      /               / 
T1 = 2   3      T2 =  4
    /
   4

下面的例子中 T2 不是 T1 的子树:

       1               3
      /                
T1 = 2   3       T2 =    4
    /
   4

代码实现:

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */
public class Solution {
    /**
     * @param T1, T2: The roots of binary tree.
     * @return: True if T2 is a subtree of T1, or false.
     */
    public boolean isSubtree(TreeNode T1, TreeNode T2) {
       //必须先判断T2,再判断T1
       if (T2 == null) {
            return true;
        }
        if (T1 == null) {
            return false;
        }

        if (isEqual(T1, T2)) {
            return true;
        }
        if (isSubtree(T1.left, T2) || isSubtree(T1.right, T2)) {
            return true;
        }
        return false;
    }

    private boolean isEqual(TreeNode T1, TreeNode T2) {
        if (T1 == null || T2 == null) {
            return T1 == T2;
        }
        if (T1.val != T2.val) {
            return false;
        }
        return isEqual(T1.left, T2.left) && isEqual(T1.right, T2.right);
    }
}

面试27:二叉树的镜像

题目:

请完成一个函数,输入一颗二叉树,该函数输出它的镜像

样例:

  1         1
 /        / 
2   3  => 3   2
   /       
  4         4

代码实现:

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */
public class Solution {
    public void invertBinaryTree(TreeNode root) {
        if (root == null) {
            return;
        }
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;

        invertBinaryTree(root.left);
        invertBinaryTree(root.right);
    } 
}

面试题28: 对称的二叉树

题目:

请实现一个函数,用来判断一颗二叉树是不是对称的。如果一颗二叉树和它的镜像一样,那么它是对称的。

样例:

    8           8          8
   /          /         /  
  6    6      6    9     7    7
 /   /     /   /    /   / 
5   7 7  5   5 7 7   5  7 7  7
3棵二叉树,其中第一棵是对称的,另外两棵不是

代码实现:

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */
public class Solution {
    public boolean isSymmetrical(TreeNode root) {
        if (root == null) {
            return true;
        }
        return check(root.left, root.right);
    }
    private boolean check(TreeNode T1, TreeNode T2) {
        if (T1 == null || T2 == null) {
            return T1 == T2;
        }
        if (T1.val != T2.val) {
            return false;
        }
        return check(T1.left, T2.right) && check(T1.right, T2.left);
    }
}

面试题33:二叉搜索树的后序遍历序列

发表评论

电子邮件地址不会被公开。 必填项已用*标注