未分類

Construct Binary Tree from Preorder and Inorder Traversal

Array, DepthFirstSearch, Go, LeetCode, Tree

Construct Binary Tree from Preorder and Inorder 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.

提示 解題應用
DepthFirstSearch PreorderTravel/InorderTravel

Default:

1
2
3
4
5
6
7
8
9
10
11
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func buildTree(preorder []int, inorder []int) *TreeNode {
}

解答思路:

這次要透過前序遍歷與中序遍歷的結果來還原成一棵二元樹，但是要注意到是還原成二元樹並不是二元搜尋樹，也就是說沒有經過排序，所以中序遍歷的參數才不是由小至大排序的結果，至於要如何透過這兩個線索來還原，前序遍歷的陣列值最主要就是能依序取得樹的根節點，而中序遍歷則是能藉由根節點的值來知道左右子樹有哪些節點值(根節點值左邊全部的值就是左子樹的節點值，反之右邊全部的值就是右子樹的節點值)，如下(因數字無關排序，以英文表示):

  • 前序遍歷: “G” DAFEMHZ

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

一開始先透過前序遍歷依序取得樹的根節點，首先是G為根節點

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

1
2
3
       G
   ↙	    ↘
ADEF       HMZ

  • 前序遍歷: G “D” AFEMHZ

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

接著因為前序遍歷取得的根節點是D所以先處理左子樹(透過遞回將左右子樹視為樹來分別處理)

1
2
3
4
5
           G
       ↙     ↘
      D	    HMZ
   ↙    ↘
A         EF

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

程式碼解說:

因為是直接藉由前序遍歷與中序遍歷的結果來還原成一棵二元樹，所以一開始便直接將前序遍歷與中序遍歷的陣列帶入遞回函數中，而這邊還要多帶一個變數用來標示目前在前序遍歷陣列中所取出的根節點值到了第幾個，以利我們在同時遞回還原左右子樹時仍能順利的從中依序取出根節點值

1
2
3
4
func buildTree(preorder []int, inorder []int) *TreeNode {
	var preTravel int
	return construct(&preTravel, preorder, inorder)
}

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func construct(preTravel *int, preorder []int, inorder []int) *TreeNode {
	if len(inorder) == 0 {
		return nil
	}
	var left *TreeNode
	var right *TreeNode
	root := preorder[*preTravel]
	*preTravel++
	for i, v := range inorder {
		if root == v {
			left = construct(preTravel, preorder, inorder[:i])
			right = construct(preTravel, preorder, inorder[i+1:])
			break
		}
	}
	return &TreeNode{root, left, right}
}

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func buildTree(preorder []int, inorder []int) *TreeNode {
	var preTravel int
	return construct(&preTravel, preorder, inorder)
}
func construct(preTravel *int, preorder []int, inorder []int) *TreeNode {
	if len(inorder) == 0 {
		return nil
	}
	var left *TreeNode
	var right *TreeNode
	root := preorder[*preTravel]
	*preTravel++
	for i, v := range inorder {
		if root == v {
			left = construct(preTravel, preorder, inorder[:i])
			right = construct(preTravel, preorder, inorder[i+1:])
			break
		}
	}
	return &TreeNode{root, left, right}
}

總結:

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

分享到