5

leetCode解题报告之构造二叉树(递归)

 3 years ago
source link: https://blog.csdn.net/ljphhj/article/details/22090255
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
leetCode解题报告之构造二叉树(递归)_快乐de胖虎-CSDN博客

此博文主要讲述了构造二叉树的两种方法：

1、通过先序和中序构造出二叉树( 来自leetCode OJ上的 题目：Construct Binary Tree from Preorder and Inorder Traversal )

2、通过后序和中序构造出二叉树( 来自leetCode OJ上的 题目：Construct Binary Tree from Inorder and Postorder Traversal)

这两题的解法类似，下面我来详细讲下如何通过

二叉树的先序序列和中序序列来构造出二叉树，至于后序序列和中序序列就不着重讲了哈！

题目：

Given preorder and inorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

分析：

题目要求我们通过中序序列和先序序列来构造出这棵二叉树，返回它的根节点。

那么我们先模拟随便画出一棵二叉树来，再把它的先序，中序，后序全部写出来

int[] preOrder = new int[]{7,-10,-4,3,-1,2,-8,11};

int[] postOrder = new int[]{-4,-1,3,-10,11,-8,2,7};
int[] inOrder = new int[]{-4,-10,3,-1,7,11,-8,2};

解题思路：

如上，我们得到了一棵二叉树的先序序列preOrder = {7,-10,-4,3,-1,2,-8,11};和中序序列inOrder = {-4,-10,3,-1,7,11,-8,2};

我们想要构建出这棵二叉树，那么我采用递归的方法来确定出每个结点和结点间的关系

通过先序序列{7,-10,-4,3,-1,2,-8,11}，我们可以知道，第一个结点7肯定是二叉树的根结点，而第二个结点-10，有可能是根结点的左子树的根结点，也有可能是右子树的根结点（具体得看中序序列中的 "7" 左边是否还有其他的结点值，或者右边是否还有其他的结点值），居然这个大问题可以被分解成小问题，我们选择采用递归的方式来解决这个问题

1. 首先通过preOrder序列，得到根结点root！

2. 递归求出root的左子树

3. 递归求出root的右子树

4. 将左子树的根结点赋值给root.left,  右子树的根结点赋值给root.right

AC代码（Construct Binary Tree from Preorder and Inorder Traversal ）:

AC代码（Construct Binary Tree from Inorder and Postorder Traversal)

博主算法方面比较薄弱，写得不好，欢迎大家给我留言哈！！！


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK