# binary tree 的DFS深度優先算法

[toc]

1.每次遞迴到最後的時候，檢查是否還有子樹
2.沒有的話就認定為leaf

每次都從左子樹走到底，然後 再依序換右子樹，一次路徑到底就return last leaf 。

## core

from collections import deque
class TreeNode:  
  def __init__(self,data):
    self.data=data 
    self.right=None  
    self.left=None 


root=TreeNode("A")
left_1=TreeNode("B")
right_1=TreeNode("C")

root.left=left_1 
root.right=right_1 

left_2=TreeNode("D")
left_1.right=left_2

def DFS_(root):
    # 每次遞迴到最後的時候，檢查是否還有子樹
    #沒有的話就認定為leaf 
    
    print(root.data)  # 這個是遍歷DFS
    if root :
        return 
    
    if not root.right and not root.left : 
    print("found a leaf",root.data)
    return 


  if root.left : 
    DFS_(root.left)

  if root.right :
    DFS_(root.right)
  return 


DFS_(root)