day11

今日day11：三種二叉樹(shù)的遍歷方式
1 首先是遞歸遍歷。需要首先搞懂前序中序后序遍歷的意思，即以根root的位置為準(zhǔn)
前序即根左右中序即左根右后序即左右根
遞歸則是指在函數(shù)中循環(huán)調(diào)用自身直至跳出遞歸條件
python實(shí)現(xiàn)
原理僅有遍歷順序的變化為區(qū)別，首先聲明一個(gè)空res數(shù)組用以存放數(shù)值，遍歷即依次獲取樹(shù)各節(jié)點(diǎn)的值，遞歸的條件是root仍然存在，由于二叉樹(shù)的各子樹(shù)仍然滿足二叉樹(shù)之定義因此當(dāng)訪問(wèn)到根時(shí)就將值送入res數(shù)組，再調(diào)整root去找左右節(jié)點(diǎn)，而左右節(jié)點(diǎn)為根時(shí)仍然滿足二叉樹(shù)定義即實(shí)現(xiàn)了遍歷

# 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
"前序"
class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        res = []
        def dfs(root):
            if root:
                res.append(root.val)
                dfs(root.left)
                dfs(root.right)
        dfs(root)
        return res
"中序"
class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        res = []
        def dfs(root):
            if root:
                dfs(root.left)
                res.append(root.val)
                dfs(root.right)
        dfs(root)
        return res
"后序"
class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        res = []
        def dfs(root):
            if root:
                dfs(root.left)
                dfs(root.right)
                res.append(root.val)
        dfs(root)
        return res

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

 //前序
 func preorderTraversal(root *TreeNode) []int {
    var dfs func(node *TreeNode)
    var res []int
    dfs = func(node *TreeNode){
        if node == nil {
            return
        }
        res = append(res,node.Val)
        dfs(node.Left)
        dfs(node.Right)
    }
    dfs(root)
    return res
}

//中序
func inorderTraversal(root *TreeNode) []int {
    var dfs func(node *TreeNode)
    var res []int
    dfs = func(node *TreeNode){
        if node == nil{
            return
        }
        dfs(node.Left)
        res = append(res,node.Val)
        dfs(node.Right)
 }
 dfs(root)
 return res
}

//后序
func postorderTraversal(root *TreeNode) []int {
    var dfs func(node *TreeNode)
    var res []int
    dfs = func(node *TreeNode){
        if node == nil {
            return 
        }
        dfs(node.Left)
        dfs(node.Right)
        res = append(res,node.Val)
    }
    dfs(root)
    return res
}

2 其次是迭代遍歷，該法旨在使用棧作為暫存值的結(jié)構(gòu)并根據(jù)遍歷順序適當(dāng)調(diào)整

"先使用數(shù)組存儲(chǔ)root，一旦其存在就將值彈出即先進(jìn)后出，再將其追加至result中，然后由于棧是先進(jìn)先出，所以先右后左"
"先序"
class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []
        stack = [root]
        result =[]

        while stack:
            node = stack.pop()
            result.append(node.val)
            if node.right:
                stack.append(node.right)
            if node.left:
                stack.append(node.left)
        return result

"中序"
"先不要將root放入stack中，使用指針指向root以供操作，該方法旨在先將根加入棧中再訪問(wèn)其左節(jié)點(diǎn)然后先出左節(jié)點(diǎn)后此時(shí)又指向右節(jié)點(diǎn)，再令其找右節(jié)點(diǎn)如上操作，則完成了中序"
class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []
        stack = []
        result = []
        cur = root
        while cur or stack:
            if cur:
                stack.append(cur)
                cur = cur.left
            else:
                cur = stack.pop()
                result.append(cur.val)
                cur = cur.right
        return result
"后序"
"基本操作如前序，但考慮到棧的先進(jìn)先出，我們將其位置調(diào)整為根右左并反轉(zhuǎn)，這樣就成為了左右根"
class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []
        stack = [root]
        result = []
        while stack:
            node = stack.pop()
            result.append(node.val)
            if node.right:
                stack.append(node.right)
            if node.left:
                stack.append(node.left)
        return result[::-1]

//先序
//借助雙端鏈表list及其中的函數(shù)
func preorderTraversal(root *TreeNode) []int {
    ans := []int{}
    if root == nil {
        return ans
    }
    st:=list.New()
    //尾插root
    st.PushBack(root)

    for st.Len() > 0{
        //彈出末尾節(jié)點(diǎn)并聲明其類型為treenode
        node := st.Remove(st.Back()).(*TreeNode)
        ans = append(ans,node.Val)
        if node.Right != nil{
            st.PushBack(node.Right)
        }
        if node.Left != nil {
            st.PushBack(node.Left)
        }
    }
    return ans
}

//中序
func inorderTraversal(root *TreeNode) []int {
    ans :=[]int{}
    if root == nil{
        return ans
    }
    st := list.New()
    cur := root
    for cur != nil || st.Len() > 0 {
        if cur!=nil{
            st.PushBack(cur)
            cur = cur.Left
        }else{
            cur = st.Remove(st.Back()).(*TreeNode)
            ans = append(ans,cur.Val)
            cur = cur.Right
        }
    }
    return ans
}

//后序
func postorderTraversal(root *TreeNode) []int {
    ans := []int{}
    if root == nil {
        return ans
    }
    st := list.New()
    st.PushBack(root)
    for st.Len() >0 {
        node := st.Remove(st.Back()).(*TreeNode)
        ans = append(ans,node.Val)
        if node.Left != nil{
            st.PushBack(node.Left)
        } 
        if node.Right != nil{
            st.PushBack(node.Right)
        }
    }
    reverse(ans)
    return ans
}

func reverse(a []int) {
    l,r := 0,len(a)-1
    for l < r {
        a[l],a[r] = a[r],a[l]
        l,r = l+1,r-1
    }
}

3 最后是統(tǒng)一迭代法：

"前序"
"類似使用棧進(jìn)行遍歷并考慮出棧順序，但它把元素入結(jié)果集的操作統(tǒng)一進(jìn)行，先完成元素的順序?qū)ふ?
class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        result = []
        st = []
        if root:
            st.append(root)
        while st:
            node = st.pop()
            if node != None:
                if node.right:
                    st.append(node.right)
                if node.left:
                    st.append(node.left)
                st.append(node)
                st.append(None)
            else:
                node = st.pop()
                result.append(node.val)
        return result

"中序"
class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        result = []
        st = []
        if root:
            st.append(root)
        while st:
            node = st.pop()
            if node != None:
                if node.right:
                    st.append(node.right)
                st.append(node)
                st.append(None)

                if node.left:
                    st.append(node.left)
            else:
                node = st.pop()
                result.append(node.val)
        return result
"后序"
class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        result = []
        st = []
        if root:
            st.append(root)
        while st:
            node = st.pop()
            if node != None:
                st.append(node)
                st.append(None)
                if node.right:
                    st.append(node.right)
                if node.left:
                    st.append(node.left)
            else:
                node = st.pop()
                result.append(node.val)
        return result

//前序
func preorderTraversal(root *TreeNode) []int {
    if root == nil {
        return nil
    }
    var stack = list.New()
    res:=[]int{}
    stack.PushBack(root)
    var node *TreeNode
    for stack.Len() > 0{
        e := stack.Back()
        stack.Remove(e)//彈出元素
        if e.Value == nil { //如果為空，則表明需要處理中間節(jié)點(diǎn)
            e = stack.Back()//彈出元素
            stack.Remove(e)//刪除中間節(jié)點(diǎn)
            node = e.Value.(*TreeNode) 
            res = append(res,node.Val)//將中間節(jié)點(diǎn)加入到結(jié)果集合中
            continue //繼續(xù)彈出下一個(gè)
        }
        node = e.Value.(*TreeNode)
        if node.Right != nil {
            stack.PushBack(node.Right)
        }
        if node.Left !=nil {
            stack.PushBack(node.Left)
        }
        stack.PushBack(node)
        stack.PushBack(nil)
    }
    return res
}
//中序
func inorderTraversal(root *TreeNode) []int {
    if root == nil {
        return nil
    }
    stack := list.New()
    res :=[]int{}
    stack.PushBack(root)
    var node *TreeNode
    for stack.Len() >0 {
        e := stack.Back()
        stack.Remove(e)
        if e.Value == nil {
            e = stack.Back()
            stack.Remove(e)
            node = e.Value.(*TreeNode)
            res = append(res,node.Val)
            continue
        }
        node = e.Value.(*TreeNode)
        if node.Right!=nil {
            stack.PushBack(node.Right)
        }
        stack.PushBack(node)
        stack.PushBack(nil)
        if node.Left != nil{
            stack.PushBack(node.Left)
        }
    }
    return res
}
//后序
func postorderTraversal(root *TreeNode) []int {
    if root == nil {
        return nil
    }
    var stack = list.New()
    res :=[]int{}
    stack.PushBack(root)
    var node *TreeNode
    for stack.Len() >0 {
        e := stack.Back()
        stack.Remove(e)
        if e.Value == nil {
            e = stack.Back()
            stack.Remove(e)
            node = e.Value.(*TreeNode)
            res=append(res,node.Val)
            continue
        }
        node = e.Value.(*TreeNode)
        stack.PushBack(node)
        stack.PushBack(nil)
        if node.Right!=nil{
            stack.PushBack(node.Right)
        }
        if node.Left!= nil {
            stack.PushBack(node.Left)
        }
    }
    return res
}

posted on 2024-06-11 19:59 leusure45 閱讀(24) 評(píng)論(0) 收藏舉報(bào)

刷新頁(yè)面返回頂部

導(dǎo)航

day11