数据结构算法（九） 之 树的 2 道面试题 62 & 6

• 剑指 Offer 面试题 62（Java 版）：序列化二叉树

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

思路： 如果二叉树的序列化是从根结点开始的话，那么相应的反序列化在根结点的数值读出来的时候就可以开始了。因此我们可以根据前序遍历的顺序来序列化二叉树，因为前序遍历是从根结点开始的。当在遍历二叉树碰到 NULL 指针时，这些 NULL 指针序列化成一个特殊的字符（比如 null）。另外，结点的数值之间要用一个特殊字符（比如 ’,’）隔开。

show my code

/**
 * 二叉树的序列化和反序列化
 * @author innovator
 *
 */
public class TreeSeriaze {

    /**
     * 序列化二叉树
     * @param root
     * @return 前序遍历序列
     */
    public static List<Integer> serializeTree(BinaryTreeNode root){
        
        if(root == null){
            return null;
        }
        
        List<Integer> result = new ArrayList<>();
        List<BinaryTreeNode> list = new ArrayList<>();
        //前序遍历序列化
        list.add(root);
        
        while(!list.isEmpty()){
            BinaryTreeNode node = list.remove(0);
            
            if(node == null){
                //为空的话就填充 null
                result.add(null);
            }else{
                result.add(node.value);
                
                //前序遍历左结点
                list.add(node.leftNode);
                //前序遍历右结点
                list.add(node.rightNode);
            }
        }
        
        return result;
        
    }
    
    /**
     * 反序列化
     * @param result
     * @return
     */
    public static BinaryTreeNode deSerialize(List<Integer> result,int index){
        
        if (result.size() < 1 || index < 0 || result.size() <= index || result.get(index) == null) {
            return null;
        }
        
        //重建二叉树，从根结点开始
        BinaryTreeNode root = new BinaryTreeNode(result.get(index));
        // 左子结点
        root.leftNode = deSerialize(result, index*2 +1);  //隔两个位置
        root.rightNode = deSerialize(result, index*2 +2);
        
        return root;
    }
    
    /**
     * 前序遍历打印
     * @param root
     */
    public static void printPreOrder(BinaryTreeNode root){
        
        if(root == null){
            System.out.printf("null ");
            return;
        }
        
        System.out.print(root.value+ " ");
        
        printPreOrder(root.leftNode);
        
        printPreOrder(root.rightNode);
        
    }
    
    
    
    //                  8
    //          6                    10
    //     5         7          9          11
    
    public static void main(String[] args){
    
        BinaryTreeNode root =  new BinaryTreeNode(8);
        BinaryTreeNode node1 = new BinaryTreeNode(6);
        BinaryTreeNode node2 = new BinaryTreeNode(10);
        BinaryTreeNode node3 = new BinaryTreeNode(5);
        BinaryTreeNode node4 = new BinaryTreeNode(7);
        BinaryTreeNode node5 = new BinaryTreeNode(9);
        BinaryTreeNode node6 = new BinaryTreeNode(11);
    
        root.leftNode = node1;
        root.rightNode = node2;
        node1.leftNode = node3;
        node1.rightNode = node4;
        node2.leftNode = node5;
        node2.rightNode = node6;
    
        System.out.println("序列化之前的前序遍历序列");
        printPreOrder(root);
        System.out.println("");
        
        List<Integer> tree = new ArrayList<>();
        tree = serializeTree(root);
        System.out.println("序列化的序列");
        for(Integer i:tree){
            if(i == null){
                System.out.print("null ");
            }else{
                System.out.print(i+" ");
            }
        }
        System.out.println("");
        BinaryTreeNode node = deSerialize(tree, 0);
        System.out.println("序列化之后的前序遍历序列");
        printPreOrder(node);
    }
    
}

结果

• 剑指 Offer 面试题 63（Java 版）：二叉树搜索第 k 个结点

题目：给定一棵二叉搜索树，请找出其中第 k 大的结点。

思路： 如果按照中序遍历的顺序遍历一棵二叉搜索树，遍历序列的数值是递增排序的。只需要用中序遍历算法遍历一棵二叉搜索树，就很容易找出它的第 k 大的结点。

show my code

/**
 * 二叉搜索树的第  k 个结点
 * @author innovator
 *
 */
public class SearchTreeNode {

    /**
     * 从小打到大排列，找到第  k 个结点
     * 中序遍历
     * @param root
     * @param k
     * @return
     */
    public static BinaryTreeNode kthNode(BinaryTreeNode root,int k){
        if(root == null || k <= 0){
            return null;
        }
        
        //由于要在后续修改计数器 k 的值，所以用数组装着
        int[] temp = {k};
        return kthCore(root, temp);
    }
    
    /**
     * 中序遍历二叉搜索树
     * @param root
     * @param k
     * @return
     */
    public static BinaryTreeNode kthCore(BinaryTreeNode root, int[] k){
        

        BinaryTreeNode target = null;
        
        //先在左子树找
        if(root.leftNode != null){
             target = kthCore(root.leftNode,k);
        }
        
        //左子树没找到
        if(target == null){
            // 说明当前的根结点是所要找的结点
            if(k[0] == 1){
                target = root;
            }else{
                // 当前的根结点不是要找的结点，但是已经找过了，所以计数器减一
                k[0] --;
            }
        }
        
        //左子树和根结点已经遍历完了
        if(target == null && root.rightNode != null){
            target = kthCore(root.rightNode, k);
        }
        
        return target;
    }
    
//                  8
//          6                    10
//     5         7          9          11

    public static void main(String[] args){
    
        BinaryTreeNode root =  new BinaryTreeNode(8);
        BinaryTreeNode node1 = new BinaryTreeNode(6);
        BinaryTreeNode node2 = new BinaryTreeNode(10);
        BinaryTreeNode node3 = new BinaryTreeNode(5);
        BinaryTreeNode node4 = new BinaryTreeNode(7);
        BinaryTreeNode node5 = new BinaryTreeNode(9);
        BinaryTreeNode node6 = new BinaryTreeNode(11);
        
        root.leftNode = node1;
        root.rightNode = node2;
        node1.leftNode = node3;
        node1.rightNode = node4;
        node2.leftNode = node5;
        node2.rightNode = node6;
        
        System.out.printf("第%d大的值为："+kthNode(root, 3).value,3);
    }

}

结果