iT邦幫忙

2021 iThome 鐵人賽

DAY 28
0
Software Development

算法30天系列 第 28

Day. 28 Recover Binary Search Tree

Leetcode #99. Recover Binary Search Tree

https://ithelp.ithome.com.tw/upload/images/20211005/20129767ooaIBrEzex.png

簡單來說二元樹裡面,有兩個node的值位置是錯的,請把它糾正回來
像例子1,3在1的左邊,不合二元樹的特性,所以1跟3交換,這樣就符合二元樹的特性。


防雷
防雷
防雷


大家還記得InOrder的走訪嗎?
它會照著值的順序,我們只要找到不照順序的值,把它記下來,最後做交換就可以解決了

例1

     2
    / \
   3   1

firstNode, secondNode用來記需要交換的兩個node
以InOrder的順序output: [3,2,1]
正確的二元樹每一個值都會比前面的小,當2發現前面的是3比自己大,我們把3記在firstNode,2記在secondNode,到1的位置發現2比較大,firstNode的位置已經有了,所以一樣放在secondNode。
最後3跟1交換

例2

      3
    /   \
   1     4
        /
       2

以InOrder的順序output: [1,3,2,4]
2比3小,firstNode=3,secondNode=2,最後交換。

程式

func recoverTree(root *TreeNode) {
	var firstNode, secondNode, preNode *TreeNode
	InOrderDFS(root, &preNode, &firstNode, &secondNode)

	firstNode.Val, secondNode.Val = secondNode.Val, firstNode.Val
}

func InOrderDFS(node *TreeNode, preNode, firstNode, secondNode **TreeNode) {
	if node == nil {
		return
	}

	InOrderDFS(node.Left, preNode, firstNode, secondNode)

	if *preNode != nil && node.Val < (*preNode).Val {
		if *firstNode == nil {
			*firstNode = *preNode
		}
		*secondNode = node
	}

    // 這一行很重要 前一個節點要用InOrder的順序
	*preNode = node

	InOrderDFS(node.Right, preNode, firstNode, secondNode)
}

上一篇
Day. 27 Binary Tree Level Order Traversal
下一篇
Day.29 其他樹的介紹
系列文
算法30天30

尚未有邦友留言

立即登入留言