Construct Binary Tree from Inorder and Postorder Traversal

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

Note:

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

提示	解題應用
DepthFirstSearch	InorderTravel/PostorderTravel

Default:

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func buildTree(inorder []int, postorder []int) *TreeNode {

}

解答思路:

先前有一篇Construct Binary Tree from Preorder and Inorder Traversal是透過前序遍歷與中序遍歷的結果來還原成一棵二元樹，而這次則是要透過中序遍歷與後序遍歷的結果來還原，中序遍歷仍是能藉由根節點的值來知道左右子樹有哪些節點值，後序遍歷雖然與前序遍歷一樣能藉由規律取得樹的根節點，不過這次不需要像前序遍歷一樣依序取出，後續遍歷的根節點一直都放在最後頭，如下:

• 中序遍歷: “ADEF” G ‘HMZ’

• 後序遍歷: AEFDHZM “G”

一開始先透過後序遍歷陣列的最後一個值取得樹的根節點，首先是G為根節點

再來藉由根節點的值透過中序遍歷來知道左右子樹有哪些節點值，透過G的根節點得知左子樹有ADEF的節點值，右子樹有HMZ

       G
   ↙	    ↘
ADEF       HMZ

• 左子樹的中序遍歷: “A” D ‘EF’

• 左子樹的後序遍歷: AEF “D”

接著因為從先前中序遍歷知道了左子樹有哪些節點值之後，再對照後序遍歷發現剛好是最前面的4個節點值，而該4個節點值在後序遍歷的陣列中排在最後一個為D，所以D就作為根節點並一樣透過該節點劃分左右子樹的節點值

           G
       ↙     ↘
      D	    HMZ
   ↙    ↘
A         EF

後面的細節就不再全數推倒，總而言之就是從後序遍歷取出最後一個值作為樹的根節點，再至中序遍歷來推得左右子樹分別有哪些節點值，最後就是透過遞回來構成一棵二元樹。

程式碼解說:

因為是直接藉由中序遍歷與後序遍歷的結果來還原成一棵二元樹，所以一開始便直接將中序遍歷與後序遍歷的陣列帶入遞回函數中

func buildTree(inorder []int, postorder []int) *TreeNode {
	return construct(inorder, postorder)
}

接下來就是遞回還原二元樹的處理，如果中序遍歷的陣列結果為空，表示此節點不存在直接回傳nil位址，而如果不為空則從後序遍歷陣列中取出最後一個值作為根節點，並從中序遍歷的陣列中尋找根節點值所在的位置以得知左右子樹有哪些節點值，這邊就單純用迴圈一個個比較直到發現相同值為止，此時就再次往下遞回左右子樹，並記得將中序遍歷陣列的根節點值左側全部帶入左子樹，根節點值右側全部帶入右子樹，後序遍歷陣列則是取陣列中最前面與中序遍歷陣列根節點值左側相同數量的值帶入左子樹，中序遍歷陣列根節點值右側相同數量的值帶入右子樹(從最前面左側相同數量的值後頭開始算才是屬於右側，到倒數第二個值因為最後一個值就是根節點的值)，待兩側子樹的位址回來，最後才向上回傳新建的根節點位址並嫁接左右子樹

func construct(inorder []int, postorder []int) *TreeNode {
	if len(inorder) == 0 {
		return nil
	}
	var left *TreeNode
	var right *TreeNode
	var leftInOrder []int
	root := postorder[len(postorder)-1]
	for i, v := range inorder {
		if root == v {
			leftInOrder = inorder[:i]
			left = construct(leftInOrder, postorder[:len(leftInOrder)])
			right = construct(inorder[i+1:], postorder[len(leftInOrder):len(postorder)-1])
			break
		}
	}
	return &TreeNode{root, left, right}
}

完整程式碼:

func buildTree(inorder []int, postorder []int) *TreeNode {
	return construct(inorder, postorder)
}
func construct(inorder []int, postorder []int) *TreeNode {
	if len(inorder) == 0 {
		return nil
	}
	var left *TreeNode
	var right *TreeNode
	var leftInOrder []int
	root := postorder[len(postorder)-1]
	for i, v := range inorder {
		if root == v {
			leftInOrder = inorder[:i]
			left = construct(leftInOrder, postorder[:len(leftInOrder)])
			right = construct(inorder[i+1:], postorder[len(leftInOrder):len(postorder)-1])
			break
		}
	}
	return &TreeNode{root, left, right}
}

總結:

要透過中序遍歷與後序遍歷的結果來還原成一棵二元樹，主要就是從後序遍歷取出最後一個值作為樹的根節點，再至中序遍歷來推得左右子樹分別有哪些節點值，最後就是透過遞回來構成一棵二元樹。