資料結構經典 在二元搜尋樹BST中搜索目標值_Leetcode #700_Leetcode精選75題

Kayla Farmer on Unsplash

題目敘述

題目會給我們一棵二元搜索樹的根結點root，還有一個指定的目標值val。

要求我們找出在樹中對應到目標值val的節點，假如找不到，請回傳null( null在Python就是None)。

題目的原文敘述

測試範例

Example 1:

Input: root = [4,2,7,1,3], val = 2
Output: [2,1,3]

Example 2:

Input: root = [4,2,7,1,3], val = 5
Output: []

約束條件

• The number of nodes in the tree is in the range [1, 5000].

節點總數目介於 1 ~ 5000 之間。

• 1 <= Node.val <= 10^7

節點值都介於1 ~ 一千萬 之間。

• root is a binary search tree.

root是一棵二元搜索樹的根節點。

• 1 <= val <= 10^7

目標值val介於1 ~ 一千萬 之間。

演算法 依照二元搜索樹BST定義的即可

讓我們回顧二元搜索樹Binary search tree的定義:

所有左子樹的節點值都比根結點還小。

所有右子樹的節點值都比根結點還大。

每一層，就先判斷是不是已經找到val目標節點了?

假如找到了，就值接回傳當下的節點。