树的遍历-已知中序+(前序|后序）求层次遍历

时间：2022-11-24 12:36:38

先来看一道题目：

L2-2. 树的遍历

时间限制400 ms
内存限制65536 kB
代码长度限制8000 B
判题程序Standard作者陈越

给定一棵二叉树的后序遍历和中序遍历，请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。

输入格式：

输入第一行给出一个正整数N（<=30），是二叉树中结点的个数。第二行给出其后序遍历序列。第三行给出其中序遍历序列。数字间以空格分隔。

输出格式：

在一行中输出该树的层序遍历的序列。数字间以1个空格分隔，行首尾不得有多余空格。

输入样例：
7
2 3 1 5 7 6 4
1 2 3 4 5 6 7
输出样例：
4 1 6 3 5 7 2

首先我们先看一下已知前序，中序。求后序遍历的结果。

package com.zjianhao.tree;


/**
 * Created by 张建浩（Clarence) on 2016-5-22 21:21.
 * the author's website:http://www.zjianhao.cn
 * the author's github: https://github.com/zhangjianhao
 */

public class Tree {

    private static int [] L = {4,1,8,3,2,6,5,7};
    private int [] V = {8,1,2,3,4,5,6,7};
    private static int [] R = {8,2,3,1,5,7,6,4};
    public static void main(String[] args) {
        Tree tree = new Tree();
        tree.solvePostOrder(0,0,L.length);

    }




    /**
     *已知前序遍历，中序遍历，求后序遍历
     * @param preStart
     * @param inStart
     * @param length
     */
    public void solvePostOrder(int preStart,int inStart,int length){
        if (length<=0)
            return;
        int v = L[preStart];
        int len = getLength(inStart,length,v);//获取左子树的长度len，则右子树的长度为length-len-1
        solvePostOrder(preStart+1,inStart,len);//递归解决左子树
        solvePostOrder(preStart+len+1,inStart+len+1,length-len-1);//右子树
        System.out.print(v+" ");//打印根节点

    }


    public int getLength(int start,int length,int v){//根据中间节点，求左子树的长度
        for (int i = start,count = 0; count<length; i++,count++){
            if (V[i] == v)
                return count;
        }
        return 0;
    }

}

已知中序，后序遍历，求前序遍历结果。

此处post初始传值为：后序的长度-1，即后序最后一个元素的索引。因为后序遍历的顺序为：左右中（LRV)所以根节点必然是最后一个，因此我们要从后往前寻找。

 public void solvePreOrder(int post,int inStart,int length){
        if (length<=0)
            return ;
        int v = R[post];
        System.out.print(v+" ");//
        int len = getLength(inStart,length,v);//left tree length
        solvePreOrder(post-(length-len),inStart,len);//solve left tree
        solvePreOrder(post-1,inStart+len+1,length-len-1);//solve right tree
    }

好了，由中序加任意遍历次序我们全部都解决了。现在我们来看一下题目。

题目中要求层次遍历。我们可以尝试由后续和中序遍历构造出一棵树来，树的层次遍历就很容易了。

首先我们需要对上述已知后序中序遍历的情况的代码稍作修改

首先定义一个节点类：

 private class Node<E>{
         E data;
         Node left;
         Node right;
    }


 public Node<Integer> solvePreOrder(int post,int inStart,int length){
        if (length<=0)
            return null;
        int v = R[post];
        Node<Integer> root = new Node<>();
        root.data = v;
        int len = getLength(inStart,length,v);//left tree length
        root.left = solvePreOrder(post-(length-len),inStart,len);//solve left tree，记录根节点的左子树
        root.right = solvePreOrder(post-1,inStart+len+1,length-len-1);//solve right tree <span style="font-family: Arial, Helvetica, sans-serif;">记录根节点的右子树</span>

        return root;
    }
构造完树后，我们按照层次遍历的结果对树进行遍历，树的层次遍历代码我们应该都很熟悉了： 

public void solveLevelOrder(int post,int inStart,int length){
        //
        Node<Integer> root = solvePreOrder(post,inStart,length);
        Queue<Node> queue = new LinkedList<>();
        System.out.println(root.left.data+":"+root.right.data);
        queue.add(root);
        while (!queue.isEmpty()){
            Node<Integer> rt = queue.poll();
            System.out.print(rt.data+" ");
            if (rt.left != null){
                queue.add(rt.left);
            }
            if (rt.right != null){
                queue.add(rt.right);
            }
        }
    }
这样我们便完成了已知后序，中序遍历，求层次遍历的结果。同理，我们对已知前序，中序，求后序遍历的代码稍作修改，便可以求出已知前序，中序遍历，求层次遍历的结果

这里便不再累述。




标签：

相关文章