個(gè)人中心
退出
劍指offer之重建二叉樹(shù)
1 問(wèn)題
重建二叉樹(shù)：給定二叉樹(shù)的先序遍歷（根左右）和中序（左中右）遍歷結(jié)果，建立這棵二叉樹(shù)。輸入保證二叉樹(shù)無(wú)重復(fù)結(jié)點(diǎn)
以先序{1, 2, 4, 7, 3, 5, 6, 8}和中序{4, 7, 2, 1, 5, 3, 8, 6}為例
2 分析
先序遍歷的特點(diǎn)，我們知道{1, 2, 4, 7, 3, 5, 6, 8}第一個(gè)元素1就是樹(shù)的根節(jié)點(diǎn)，然后中序遍歷{4, 7, 2, 1, 5, 3, 8, 6}的根節(jié)點(diǎn)在中間，因?yàn)槲覀儚南刃虮闅v里面得知1就是根節(jié)點(diǎn)，所以在中序遍歷{4, 7, 2, 1, 5, 3, 8, 6}中，在中序遍歷數(shù)組1的左邊元素都是根節(jié)點(diǎn)左子樹(shù){4, 7, 2,}，這里是3個(gè)元素，所以在先序數(shù)組里面根節(jié)點(diǎn)1的后面3個(gè)元素也是左子樹(shù){2,4,7}，也是根節(jié)點(diǎn)的左子樹(shù)，在中序遍歷1的右邊邊元素都是{5, 3, 8, 6}都是根節(jié)點(diǎn)的右子樹(shù)，然后我們?cè)谙刃驍?shù)組里面根節(jié)點(diǎn)1的后面第3個(gè)元素的后面到尾巴，也就是{3,5,6,8}也就是根節(jié)點(diǎn)的右子樹(shù)。然后我們?cè)侔褑?wèn)題分解成構(gòu)建左子樹(shù){2,4,7}和構(gòu)建右子樹(shù){3,5,6,8}，以此遞歸處理。
我們構(gòu)建左子樹(shù)
再構(gòu)建右子樹(shù)
3 代碼實(shí)現(xiàn)
import java.io.*;
class Tree
{
public int value;
public Tree left;
public Tree right;
public Tree(int value)
{
this.value = value;
this.left = null;
this.right = null;
}
/**
*前序遍歷
*/
public void printTree(Tree node)
{
if (null == node)
return;
System.out.println("value is " + node.value);
printTree(node.left);
printTree(node.right);
}
/*
*得到樹(shù)的根節(jié)點(diǎn)
*/
public Tree getTree(int[] preDatas, int[] inDatas)
{
if (null == preDatas || null == inDatas)
{
System.out.println("preDatas is null or inDatas is null");
return null;
}
Tree tree = buildTree(preDatas, 0, preDatas.length - 1, inDatas, 0, inDatas.length - 1);
return tree;
}
/*
*構(gòu)建樹(shù)的左右子結(jié)構(gòu)
*/
public Tree buildTree(int[] preDatas, int preStart, int preEnd, int[] inDatas, int inStart, int inEnd)
{
if (null == preDatas || null == inDatas)
{
System.out.println("preDatas is null or inDatas is null");
return null;
}
System.out.println("preStart is:" + preStart + " preEnd is"
+ preEnd + " inStart is " + inStart + " inEnd is" + inEnd);
//這里就是進(jìn)行如果樹(shù)的左子節(jié)點(diǎn)和右子節(jié)點(diǎn)是否為空進(jìn)行設(shè)置
if (preStart > preEnd || inStart > inEnd)
{
return null;
}
Tree tree = new Tree(preDatas[preStart]);
for (int i = inStart; i <= inEnd; ++i)
{
System.out.println("preDatas[preStart] is " + preDatas[preStart]);
if (preDatas[preStart] == inDatas[i])
{
tree.left = buildTree(preDatas, preStart + 1, preStart + i - inStart, inDatas, inStart, i - 1);
tree.right = buildTree(preDatas, preStart + i - inStart + 1, preEnd, inDatas, i + 1, inEnd);
break;
}
}
return tree;
}
}
class test
{
public static void main (String[] args) throws java.lang.Exception
{
int[] preDatas = {1, 2, 4, 7, 3, 5, 6, 8};
int[] inDatas = {4, 7, 2, 1, 5, 3, 8, 6};
Tree test = new Tree(0);
Tree tree = test.getTree(preDatas, inDatas);
if (tree == null)
{
System.out.println("tree is null");
return;
}
//我們進(jìn)行前序打印樹(shù)
test.printTree(tree);
}
}
4 運(yùn)行結(jié)果
preStart is:0 preEnd is7 inStart is 0 inEnd is7
preDatas[preStart] is 1
preDatas[preStart] is 1
preDatas[preStart] is 1
preDatas[preStart] is 1
preStart is:1 preEnd is3 inStart is 0 inEnd is2
preDatas[preStart] is 2
preDatas[preStart] is 2
preDatas[preStart] is 2
preStart is:2 preEnd is3 inStart is 0 inEnd is1
preDatas[preStart] is 4
preStart is:3 preEnd is2 inStart is 0 inEnd is-1
preStart is:3 preEnd is3 inStart is 1 inEnd is1
preDatas[preStart] is 7
preStart is:4 preEnd is3 inStart is 1 inEnd is0
preStart is:4 preEnd is3 inStart is 2 inEnd is1
preStart is:4 preEnd is3 inStart is 3 inEnd is2
preStart is:4 preEnd is7 inStart is 4 inEnd is7
preDatas[preStart] is 3
preDatas[preStart] is 3
preStart is:5 preEnd is5 inStart is 4 inEnd is4
preDatas[preStart] is 5
preStart is:6 preEnd is5 inStart is 4 inEnd is3
preStart is:6 preEnd is5 inStart is 5 inEnd is4
preStart is:6 preEnd is7 inStart is 6 inEnd is7
preDatas[preStart] is 6
preDatas[preStart] is 6
preStart is:7 preEnd is7 inStart is 6 inEnd is6
preDatas[preStart] is 8
preStart is:8 preEnd is7 inStart is 6 inEnd is5
preStart is:8 preEnd is7 inStart is 7 inEnd is6
preStart is:8 preEnd is7 inStart is 8 inEnd is7
value is 1
value is 2
value is 4
value is 7
value is 3
value is 5
value is 6
value is 8
5 總結(jié)
中途遇到這個(gè)一個(gè)錯(cuò)誤
error: <identifier> expected
是我在手寫(xiě)函數(shù)的時(shí)候參數(shù)前面忘記了定義類型，所以報(bào)這個(gè)錯(cuò)誤。
我們這里用了4個(gè)指針，分別是先序的起尾指針和中序的起尾指針，然后我們不斷更新4個(gè)指針指針的位置，然后當(dāng)先序的起指針大于尾指針的時(shí)候或者中序的起指針大于尾指針的時(shí)候我們就構(gòu)建空指針，就這樣遞歸處理就行。
作者：chen.yu
深信服三年半工作經(jīng)驗(yàn)，目前就職游戲廠商，希望能和大家交流和學(xué)習(xí),
微信公眾號(hào)：編程入門到禿頭 或掃描下面二維碼
零基礎(chǔ)入門進(jìn)階人工智能(鏈接)
分類導(dǎo)航