Leetcode:Construct Binary Tree from Preorder and Inorder Traversal

LeetCode里面的两道题:分别是根据前序遍历中序遍历求树的结构,另外一个类似的题是根据中序遍历后序遍历求树的结构。
对于这种经典的题,自然有经典的解题思路。二话不说,直接上代码,具体的解题思路,

1.树节点的定义

public class TreeNode {

    public int data;
    public TreeNode left;
    public TreeNode right;

    public TreeNode(int data) {
        this.data = data;
        this.left = null;
        this.right = null;
    }
}

2.遍历树的相关代码

public class VisitTree {

    public static void preVisit(TreeNode root) {
        if(root == null) {
            return;
        }
        System.out.print(root.data + " ");
        preVisit(root.left);
        preVisit(root.right);
    }

    public static void inVisit(TreeNode root) {
        if(root == null) {
            return;
        }
        inVisit(root.left);
        System.out.print(root.data + " ");
        inVisit(root.right);
    }

    public static void postVisit(TreeNode root) {
        if(root == null) {
            return;
        }
        postVisit(root.left);
        postVisit(root.right);
        System.out.print(root.data + " ");
    }
}

3.根据前序遍历中序遍历确定树的结构

/**
 * 我们先考察先序遍历序列和中序遍历序列的特点。
 * 对于先序遍历序列,根在最前面,后面部分存在一个分割点,前半部分是根的左子树,后半部分是根的右子树。
 * 对于中序遍历序列,根在中间部分,从根的地方分割,前半部分是根的左子树,后半部分是根的右子树。
 * 当我们从上向下构建树时,我们可以通过先序遍历序列知道根节点的值,但是如何知道两个序列是在哪里分割的呢?这就要依靠中序序列了。
 * 我们在中序序列中找到这个根的值,根据这个根的坐标,我们可以知道这个根左子树有多少个节点,右子树有多少个节点。
 * 然后我们根据这个将先序遍历序列分割,通过递归再次取每个部分的第一个作为根,
 * 同时为了下一次能准确的计算出左右子树各有多少节点,我们也要同时对中序遍历序列进行分割。
 *
 */
public class PreInOrder {

    public static int preStart = 0;

    public static TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder.length == 0 || inorder.length == 0) return null;
        return helper(0, inorder.length - 1, preorder, inorder);
    }

    private static TreeNode helper(int inStart, int inEnd, int[] preorder, int[] inorder) {
        if(preStart > preorder.length || inStart > inEnd) {
            return null;
        }

        TreeNode root = new TreeNode(preorder[preStart]);
        int inMid = 0;
        // 找到根在中序序列中的位置,从而知道先序中的分割点
        for(int i=inStart; i<=inEnd; i++) {
            if(inorder[i] == preorder[preStart]) {
                inMid = i;
            }
        }
        preStart++;
        // 例如先序序列 1(234)(567) 中2是左子树的根
        root.left = helper(inStart, inMid - 1, preorder, inorder);
        // 先序序列 1(234)(567) 中5是右子树的根
        root.right = helper(inMid + 1, inEnd, preorder, inorder);

        return root;
    }



    public static void main(String[] args) {
        int[] preorder = {1,2,4,6,7,3,5};
        int[] inorder =  {4,6,7,2,1,5,3};
        TreeNode root = buildTree(preorder, inorder);
        VisitTree.preVisit(root);
        System.out.println();
        VisitTree.inVisit(root);
        System.out.println();
        VisitTree.postVisit(root);
    }

4.根据中序遍历后序遍历确定树的结构

/**
 * 中序序列仍然是以根节点划分为左右两边,而后序序列的特点则是根在最后,然后在跟前面的那部分中,前面部分是左子树,后面的部分是右子树。
 * 所以其实我们就是把上一题给反过来了。
 * 这题我们将后序序列的指针全局化,这样我们可以先建好右子树,再建左子树,而指针只要顺序从后向前就行了。
 */
public class PostInOrder {

    public static int postEnd = 0;

    public static TreeNode buildTree(int[] postorder, int[] inorder) {
        postEnd = postorder.length - 1;
        return helper(0, inorder.length - 1, postorder, inorder);
    }

    private static TreeNode helper(int inStart, int inEnd, int[] postorder, int[] inorder) {
        if(postEnd < 0 || inStart > inEnd) {
            return null;
        }

        TreeNode root = new TreeNode(postorder[postEnd--]);
        int inMid = 0;
        for(int i=inStart; i<=inEnd; i++) {
            if(inorder[i] == root.data) {
                inMid = i;
                break;
            }
        }
        root.right = helper(inMid + 1, inEnd, postorder, inorder);
        root.left = helper(inStart, inMid - 1, postorder, inorder);
        return root;
    }

    public static void main(String[] args) {
        int[] inorder =   {4,6,7,2,1,5,3};
        int[] postorder = {7,6,4,2,5,3,1};
        TreeNode root = buildTree(postorder, inorder);
        VisitTree.preVisit(root);
        System.out.println();
        VisitTree.inVisit(root);
        System.out.println();
        VisitTree.postVisit(root);
    }
}

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 201,468评论 5 473
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 84,620评论 2 377
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 148,427评论 0 334
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 54,160评论 1 272
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 63,197评论 5 363
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,334评论 1 281
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 37,775评论 3 393
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,444评论 0 256
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 40,628评论 1 295
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,459评论 2 317
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,508评论 1 329
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,210评论 3 318
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 38,767评论 3 303
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,850评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,076评论 1 258
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 42,627评论 2 348
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,196评论 2 341

推荐阅读更多精彩内容