1，二叉樹的定義
二叉樹的結(jié)構(gòu)：二叉樹由根節(jié)點和左右子樹組成，二叉樹的左子樹和右子樹分別為二叉樹。這種結(jié)構(gòu)使得有關(guān)二叉樹的問題大部分可以用遞歸的算法解決。
2，二叉樹的序列化，使得內(nèi)存中的二叉樹可以在文件中存儲起來。
二叉樹的遍歷有：前序，中序，后序遍歷，層序遍歷。
前序遍歷（根節(jié)點->左子樹->右子樹）
中序遍歷（左子樹->根節(jié)點->右子樹）
后序遍歷（左子樹->右子樹->根節(jié)點）
層序遍歷二叉樹，即從上到下，同層節(jié)點從左到右遍歷每個節(jié)點。通常會借助“隊列”這種數(shù)據(jù)結(jié)構(gòu)，保證“先進先出”。
Python中的隊列結(jié)構(gòu)在標(biāo)準(zhǔn)庫中，from collections import deque
3，二叉樹的反序列化（重建二叉樹）
"""從前序遍歷序列和中序遍歷序列構(gòu)建二叉樹（無重復(fù)元素）
Given preorder and inorder traversal of a tree,
construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。
思路：
preorder第一個元素為root，
在inorder里面找到root，在它之前的為左子樹（長l1），之后為右子樹（長l2）。
preorder[1]到preorder[l1]為左子樹,之后為右子樹，分別遞歸。"""
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
if not preorder:
return None
root = TreeNode(preorder[0])
loc = inorder.index(preorder[0])
root.left = self.buildTree(preorder[1 : loc + 1], inorder[ : loc])
root.right = self.buildTree(preorder[loc+1 : ], inorder[loc+1: ])
return root
"從中序和后序序列構(gòu)建二叉樹"
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
if not postorder:
return None
root=TreeNode(postorder[-1])
loc = inorder.index(postorder[-1])
#inorder[:loc]#左子樹,長度為loc;postorder[:loc]
#inorder[loc+1:]#右子樹postorder[loc:-1]
root.left = self.buildTree( inorder[:loc], postorder[:loc])
root.right = self.buildTree(inorder[loc+1:], postorder[loc:-1] )
return root
3,二叉樹的鏡像（可以用遞歸來做）
二叉樹的鏡像定義：源二叉樹
8
/
6 10
/ \ /
5 7 9 11
鏡像二叉樹
8
/
10 6
/ \ /
11 9 7 5
4，判斷一顆二叉樹是否是對稱的，注意，如果一個二叉樹同此二叉樹的鏡像是同樣的，定義其為對稱的。（可以用遞歸來做）
5，判斷給定的二叉樹是否是二叉搜索樹
6.二叉樹的最大深度leetcode T104
"""二叉樹的最大深度(二叉樹的深度為根節(jié)點到最遠葉子節(jié)點的最長路徑上的節(jié)點數(shù)。)
leetcode T104
The maximum depth is the number of nodes
along the longest path from the root node down to the farthest leaf node.
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/maximum-depth-of-binary-tree
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。"""
class Solution:
def maxDepth(self, root: TreeNode) -> int:
if not root:
return 0
return max(self.maxDepth(root.left),self.maxDepth(root.right))+1
7.路徑總和
"""路徑總和
Given a binary tree and a sum,
determine if the tree has a root-to-leaf path
such that adding up all the values along the path equals the given sum.
Note: A leaf is a node with no children.
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/path-sum"""
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def hasPathSum(self, root: TreeNode, sum: int) -> bool:
if not root:
return False
if root.left == None and root.right == None:
return sum-root.val == 0
return self.hasPathSum(root.left,sum-root.val) or self.hasPathSum(root.right,sum-root.val)
8.路徑總和II
"""路徑總和II
Given a binary tree and a sum,
find all root-to-leaf paths where each path's sum equals the given sum.
Note: A leaf is a node with no children.
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/path-sum-ii
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處T113"""
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]:
res=[]#記錄所有路徑數(shù)字
path=[]#記錄每一條路徑上的數(shù)字
def help(root,sum,path):
if not root:
return []
if not root.left and not root.right and root.val == sum:
path.append(root.val)
res.append(path)
if root.left:
help(root.left,sum-root.val,path+[root.val])
if root.right:
help(root.right,sum-root.val,path+[root.val])
help(root,sum,path)
return res
另一種寫法，等同于上面
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
def help(root,s,v,target):
if not root:
return
if root.left is None and root.right is None and root.val == target:
s.append(root.val)
v.append(s)
if root.left:
help(root.left,s+[root.val],v,target-root.val)
if root.right:
help(root.right,s+[root.val],v,target-root.val)
class Solution(object):
def pathSum(self, root, sum):
"""
:type root: TreeNode
:type sum: int
:rtype: List[List[int]]
"""
s=[] #記錄每一條路徑上的數(shù)字
v=[] #記錄所有路徑數(shù)字
help(root,s,v,sum)
return v
9.二叉樹的最小深度
"""
Given a binary tree, find its minimum depth.
The minimum depth is the number of nodes
along the shortest path from the root node down to the nearest leaf node.
Note: A leaf is a node with no children.
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/minimum-depth-of-binary-tree
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。"""
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def minDepth(self, root: TreeNode) -> int:
if not root:
return 0
left=self.minDepth(root.left)
right=self.minDepth(root.right)
if left and right:
return min(left,right)+1
else:#此時right，left至少有一個樹為空
return left+right+1
2020年7月23日22:44:38
