树的不同形态

[编程题]树的不同形态

热度指数：2956 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

给定二叉树T（树深度不超过H<=10，深度从1开始，节点个数N<1024，节点编号1~N）的层序和中序遍历，输出T从左向右叶子节点以及树先序和后序遍历序列

输入描述:

输入两行，分别代表层序和中序遍历结果，节点编号按单个空格分开

输出描述:

依次输出  从左向右叶子节点 ，先序， 后序 遍历 。 节点编号按空格分开

示例1

输入

3 5 4 2 6 7 1
2 5 3 6 4 7 1

输出

2 6 1
3 5 2 4 6 7 1
2 5 6 1 7 4 3

算法知识视频讲解

Java

牛客557909886号

//层序遍历和中序遍历重建二叉树
import java.util.Arrays;
import java.util.ArrayList;
import java.util.Scanner;
public class Main{
    class TreeNode{
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
        TreeNode(int val){
            this.val = val;
        }
    }
    private ArrayList<Integer> leaves = new ArrayList<Integer>(); 
    private ArrayList<Integer> pre = new ArrayList<>();
    private ArrayList<Integer> last = new ArrayList<>();
    
    //找出数组中某个元素的坐标
    public int findIndex(int[] array, int val){
        for(int i = 0; i < array.length; i++){
            if(array[i] == val)
                return i;
        }
        return -1;
    }
    
    //重建二叉树
    public TreeNode constructT(int[] layer, int[] mid){
        if(layer.length == 0) return null;
        if(layer.length == 1){
            leaves.add(layer[0]);
            TreeNode node = new TreeNode(layer[0]);
            return node;
        }
        //根节点
        int val = layer[0];
        TreeNode root = new TreeNode(val);
        //将中序遍历根据根节点分为左右两棵子树的中序遍历
        int index = findIndex(mid, val);
        if(index == 0)
            root.left = null;
        else{
            int[] left = Arrays.copyOfRange(mid,0, index);
            //在层序遍历数组layer中找出左子树的层序遍历数组
            int[] layerl = new int[left.length];
            for(int i = 0,j=0; i < layer.length&&j < left.length;i++){
                if(findIndex(left,layer[i])!=-1){
                    layerl[j] = layer[i];
                    j++;
                }
            }
            root.left = constructT(layerl,left);
        }
        if(index == mid.length-1)
            root.right = null;
        else{
            int[] right = Arrays.copyOfRange(mid,index+1, mid.length);
            //在层序遍历数组layer中找出右子树的层序遍历数组，为了节省时间，倒序查找
            int[] layerr = new int[right.length];
            for(int i = layer.length-1,j=right.length-1; i >=0&&j >=0;i--){
                if(findIndex(right,layer[i])!=-1){
                    layerr[j] = layer[i];
                    j--;
                }
            }
            root.right = constructT(layerr,right);
        }
        return root;
    }
    
    public void preOrder(TreeNode root){
        if(root != null){
            pre.add(root.val);
            preOrder(root.left);
            preOrder(root.right);
        }
    }
    
    public void lastOrder(TreeNode root){
        if(root != null){
            lastOrder(root.left);
            lastOrder(root.right);
            last.add(root.val);
        }
    }
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        String first = in.nextLine();
        String second = in.nextLine();
        String[] f = first.split(" ");
        String[] s = second.split(" ");
        if(s.length == 0){
            System.out.println();
            System.out.println();
            System.out.println();
            return;
        }
        int[] layer = new int[f.length];
        int[] mid = new int[s.length];
        for(int i = 0; i < f.length; i++){
            layer[i] = Integer.valueOf(f[i]);
            mid[i] = Integer.valueOf(s[i]);
        }
        Main m = new Main();
        TreeNode root = m.constructT(layer,mid);
        m.preOrder(root);
        m.lastOrder(root);
        for(int i = 0; i < m.leaves.size(); i++){
            System.out.print(m.leaves.get(i)+" ");
        }
        System.out.println();
        for(int i = 0; i < m.pre.size(); i++){
            System.out.print(m.pre.get(i)+" ");
        }
        System.out.println();
        for(int i = 0; i < m.last.size(); i++){
            System.out.print(m.last.get(i)+" ");
        }
        System.out.println();
    }
}

发表于 2020-06-03 15:09:48 回复(0)

Java

蹲在厕所里数大尾巴蛆

关键问题在于根据中序和层序建树，之后的都好说了

除了建树函数，遍历前序、后序在这里均采用非递归方法

import java.util.*;
class TreeNode{
    int val;
    TreeNode left = null;
    TreeNode right = null;
    TreeNode(int val) {this.val = val;}
}
public class Main{
    public static void findLeaf(TreeNode root){
        if (root == null) return;
        TreeNode p = root;
        ArrayList<TreeNode> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
         while (!stack.isEmpty()||p != null){
            if (p != null){
                stack.push(p);
                p = p.left;
            }
            else {
                p = stack.pop();
                if (p.right == null&&p.left == null) list.add(p);
                p = p.right;
            }
        }
        for (int i=0;i<list.size();i++)
            System.out.print(list.get(i).val+" ");
        System.out.println();
    }
    public static void PrePrint(TreeNode root){
        if (root == null) return;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode p = root;
        while (p != null||!stack.isEmpty()){
            if (p != null){
                System.out.print(p.val+" ");
                stack.push(p);
                p = p.left;
            }
            else {
                p = stack.pop();
                p = p.right;
            }
        }
        System.out.println();
    }
    public static void PostPrint(TreeNode root){
        if (root == null) return;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode p = root, pL = root;
        while (p != null){
            stack.push(p);
            p = p.left;
        }
        while (!stack.isEmpty()){
            p = stack.pop();
            if (p.right == null||pL == p.right){
                System.out.print(p.val+" ");
                pL = p;
            }
            else {
                stack.push(p);
                p = p.right;
                while (p != null){
                    stack.push(p);
                    p = p.left;
                }
            }
        }
        System.out.println();
    }
    public static TreeNode reCon(int []lay, int []in){
        if (lay.length == 0) return null;
        TreeNode root = new TreeNode(lay[0]);
        ArrayList<Integer> left = new ArrayList<>();
        ArrayList<Integer> right = new ArrayList<>();
        int head = 0;
        for (;head < in.length;head++)
            if (in[head] == lay[0])
                break;
        boolean leftTree = false;
        for (int i=1;i<lay.length;i++){
            leftTree = false;
            for (int j=0;j<head;j++)
                if (lay[i] == in[j]){
                    leftTree = true;
                    break;
                }
            if (leftTree) left.add(lay[i]);
            else right.add(lay[i]);
        }
        int[] layleft = new int[left.size()];
        int[] layright = new int[right.size()];
        for (int i=0;i<left.size();i++)
            layleft[i] = left.get(i);
        for (int i=0;i<right.size();i++)
            layright[i] = right.get(i);
        root.left = reCon(layleft, Arrays.copyOfRange(in, 0, head));
        root.right = reCon(layright, Arrays.copyOfRange(in, head+1, in.length));
        return root;
    }
    public static void main(String []args){
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextLine()){
            String []laystr = sc.nextLine().split(" ");
            String []instr = sc.nextLine().split(" ");
            int []lay = new int[laystr.length];
            int []in = new int[instr.length];
            for (int i=0;i<in.length;i++){
                lay[i] = Integer.valueOf(laystr[i]);
                in[i] = Integer.valueOf(instr[i]);
            }
            TreeNode root = reCon(lay, in);
            findLeaf(root);
            PrePrint(root);
            PostPrint(root);
        }
    }
}

发表于 2019-09-24 00:59:00 回复(0)