# Definition for a binary tree node.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
# 感覺這道題不是很難，這里我是讓所有要插入的節點都放在葉子節點，
# 那么我們用遞回遍歷的時候根節點就有四種情況
# 1，根節點的值和插入節點的值，根節點大就插入到左子樹，根節點小就插入到右子樹
# 然后在判斷左右子樹是否為空，如果為空直接左右指標指向以要插入的值構造的節點，
# 否則就繼續遍歷，
class Solution:
def insertIntoBST(self, root: TreeNode, val: int) -> TreeNode:
# 首先需要判斷根節點是否為空，如果為空就直接回傳要插入的值構造的節點，
if not root: return TreeNode(val)
# 這里判斷要插入的值是要插入到左子樹還是右子樹，
if root.val >= val and root.left:
self.insertIntoBST(root.left,val)
elif root.val >= val and not root.left:
root.left = TreeNode(val)
if root.val < val and root.right:
self.insertIntoBST(root.right,val)
elif root.val < val and not root.right:
root.right = TreeNode(val)
return root
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/141678.html
標籤：其他
上一篇：學習第41天