资讯详情

Leetcode(3)——二叉树

格式：

题号 题名 简单思路 code

总结二叉树的遍历

递归解法

/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func preorderTraversal(root *TreeNode) []int { 
             ans:=[]int{ 
        }     if root==nil { 
                 return ans     }     assist(root,&ans)     return ans }  func assist(root *TreeNode,list *[]int) { 
             if root==nil { 
                 return     }     // 三种次历变化     *list=append(*list,root.Val)     assist(root.Left,list)     assist(root.Right,list) }

栈解法

  • 前序遍历(切片实现栈)
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func preorderTraversal(root *TreeNode) []int { 
             ans:=[]int{ 
        }     if root==nil { 
                 return ans     }     tmp:=[]*TreeNode{ 
        root
       
        } 
        for 
        len
        (tmp
        )
        >
        0 
        { 
          node
        :=tmp
        [
        len
        (tmp
        )
        -
        1
        ] ans
        =
        append
        (ans
        ,node
        .Val
        ) tmp
        =tmp
        [
        :
        len
        (tmp
        )
        -
        1
        ] 
        if node
        .Right
        !=
        nil 
        { 
          tmp
        =
        append
        (tmp
        ,node
        .Right
        ) 
        } 
        if node
        .Left
        !=
        nil 
        { 
          tmp
        =
        append
        (tmp
        ,node
        .Left
        ) 
        } 
        } 
        return ans 
        }
  • 前序遍历(双链表实现栈)
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */
import "container/list"
func preorderTraversal(root *TreeNode) []int { 
        
    ans:=[]int{ 
        }
    if root==nil { 
        
        return ans
    }
    tmp:=list.New()
    tmp.PushBack(root)
    for node:=tmp.Back();node!=nil;node=tmp.Back() { 
        
        value:=node.Value.(*TreeNode)
        ans=append(ans,value.Val)
        tmp.Remove(node)
        if value.Right!=nil { 
        
            tmp.PushBack(value.Right)
        }
        if value.Left!=nil { 
        
            tmp.PushBack(value.Left)
        } 
    }
    return ans
}
  • 中序遍历
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */

func inorderTraversal(root *TreeNode) []int { 
        
    ans:=[]int{ 
        }
    stack:=[]*TreeNode{ 
        }
    curr:=root
    for len(stack)>0 || curr!=nil { 
        
        for curr!=nil { 
        
            stack=append(stack,curr)
            curr=curr.Left
        }
        if len(stack)>0 { 
        
            node:=stack[len(stack)-1]
            stack=stack[:len(stack)-1]
            ans=append(ans,node.Val)
            curr=node.Right
        }
    }
    return ans
}
  • 后序遍历
  • 根-右-左的逆序，类似前序遍历
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */
func postorderTraversal(root *TreeNode) []int { 
        
    ans:=[]int{ 
        }
    if root==nil { 
        
        return ans
    }
    tmp:=[]*TreeNode{ 
        root}
    for len(tmp)>0 { 
        
        node:=tmp[len(tmp)-1]
        tmp=tmp[:len(tmp)-1]
        ans=append([]int{ 
        node.Val},ans...)
        if node.Left!=nil { 
        
            tmp=append(tmp,node.Left)
        }
        if node.Right!=nil { 
        
            tmp=append(tmp,node.Right)
        }
    }
    return ans
}

颜色标记法

  • 示前序遍历，三种遍历基本类似
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */
 type Color int
 const (
     WHITE Color=0
     BLACK Color=1
 )
func preorderTraversal(root *TreeNode) []int { 
        
    ans:=[]int{ 
        }
    if root == nil { 
        
        return ans
    }
    tmp:=[][2]interface{ 
        }{ 
        [2]interface{ 
        }{ 
        root,WHITE}}
    for len(tmp)>0 { 
        
        node:=tmp[len(tmp)-1]
        tmp=tmp[:len(tmp)-1]
        t_node:=node[0].(*TreeNode)
        if t_node==nil { 
        
            continue
        }
        if node[1].(Color)==WHITE { 
        
            // 三种遍历更改处
            tmp=append(tmp,[2]interface{ 
        }{ 
        t_node.Right,WHITE})
            tmp=append(tmp,[2]interface{ 
        }{ 
        t_node.Left,WHITE})
            tmp=append(tmp,[2]interface{ 
        }{ 
        t_node,BLACK})
        } else { 
        
            ans=append(ans,t_node.Val)
        }
    }
    return ans
}
  • 示后序遍历
type Color int
 const (
     WHITE Color=0
     BLACK Color=1
 )
func postorderTraversal(root *TreeNode) []int { 
        
    ans:=[]int{ 
        }
    if root == nil { 
        
        return ans
    }
    tmp:=[][2]interface{ 
        }{ 
        [2]interface{ 
        }{ 
        root,WHITE}}
    for len(tmp)>0 { 
        
        node:=tmp[len(tmp)-1]
        tmp=tmp[:len(tmp)-1]
        t_node:=node[0].(*TreeNode)
        if t_node==nil { 
        
            continue
        }
        if node[1].(Color)==WHITE { 
        
            tmp=append(tmp,[2]interface{ 
        }{ 
        t_node,BLACK})
            tmp=append(tmp,[2]interface{ 
        }{ 
        t_node.Right,WHITE})
            tmp=append(tmp,[2]interface{ 
        }{ 
        t_node.Left,WHITE})
        } else { 
        
            ans=append(ans,t_node.Val)
        }
    }
    return ans
}

Morris遍历

  • 参考
  • 前序遍历
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */
func preorderTraversal(root *TreeNode) []int { 
        
    ans:=[]int{ 
        }
    if root==nil { 
        
        return ans
    }
    curr:=root
    for curr!=nil { 
        
        if left:=curr.Left;left!=nil { 
        
            prev:=findPrev(curr)
            
            if prev.Right==nil { 
        
                ans=append(ans,curr.Val)
                prev.Right=curr
                curr=left
            } else { 
        
                curr=curr.Right
                prev.Right=nil
            }
        } else { 
        
            ans=append(ans,curr.Val)
            curr=curr.Right
        }
    }
    return ans
}

func findPrev(curr *TreeNode) *TreeNode { 
        
    t_node:=curr.Left
    for t_node.Right!=nil && t_node.Right!=curr { 
        
        t_node=t_node.Right
    }
    return t_node
}
  • 中序遍历
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */
func inorderTraversal(root *TreeNode) []int { 
        
    ans:=[]int{ 
        }
    if root==nil { 
        
        return ans
    }
    curr:=root
    for curr!=nil { 
        
        if left:=curr.Left;left!=nil { 
        
            prev:=findPrev(curr)
            if prev.Right==nil { 
        
                prev.Right=curr
                curr=left
            } else { 
        
                ans=append(ans,curr.Val)
                curr=curr.Right
                prev.Right=nil
            }
        } else { 
        
            ans=append(ans,curr.Val)
            curr=curr.Right
        }
    }
    return ans
}

func findPrev(curr *TreeNode) *TreeNode { 
        
    t_node:=curr.Left
    for t_node.Right!=nil && t_node.Right!=curr { 
        
        t_node=t_node.Right
    }
    return t_node
}
  • 后序遍历
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */
func postorderTraversal(root *TreeNode) []int { 
        
    ans:=[]int{ 
        }
    if root==nil { 
        
        return ans
    }
    curr:=root
    for curr!=nil { 
        
        if right:=curr.Right;right!=nil { 
        
            prev:=findPrev(curr)
            
            if prev.Left==nil { 
        
                ans=append([]int{ 
        curr.Val},ans...)
                prev.Left=curr
                curr=right
            } else { 
        
                curr=curr.Left
                prev.Left=nil
            }
        } else { 
        
            ans=append([]int{ 
        curr.Val},ans...)
            curr=curr.Left
        }
    }
    return ans
}

func findPrev(curr *TreeNode) *TreeNode { 
        
    t_node:=curr.Right
    for t_node.Left!=nil && t_node.Left!=curr { 
        
        t_node=t_node.Left
    }
    return t_node
}

层序遍历

/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */
func levelOrder(root *TreeNode) [][]int { 
        
    ans:=make([][]int,0)
    if root==nil { 
        
        return ans
    }
    arr1:=[]*TreeNode{ 
        root}  
    for len(arr1) > 0 { 
        
        tmp:=make([]int,len(arr1))
        arr2:=[]*TreeNode{ 
        }
        for idx,node := range arr1 { 
        
            tmp[idx]=node.Val
            if node.Left!=nil { 
        
                arr2=append(arr2,node.Left)
            }
            if node.Right!=nil { 
        
                arr2=append(arr2,node.Right)
            }
        }
        ans=append(ans,tmp)
        arr1=arr2
    }
    return ans
}

T96: 给出不同的二叉搜索树数目

  • 利用了BST的性质；这里为了避免重复计算，只算半边
  • 记忆化递归
  • Catalan数
var memo map[int]int=map[int]int{ 
        0:1,1:1}

func numTrees(n int) int { 
        
    if v,ok:=memo[n];ok { 
        
        return v
    }
    v:=0
    if n%2==1 { 
        
        for i:=0;i<n/2;i++ { 
        
            v+=numTrees(i)*numTrees(n-1-i)
        }
        v*=2
        v+=numTrees(n/2)*numTrees(n-1-n/2)
        
    } else { 
        
        for i:=0;i<n/2;i++ { 
        
            v+=numTrees(i)*numTrees(n-1-i)
        }
        v*=2
    }
    memo[n]=v
    return v
}

T95: 给出不同的二叉搜索树

  • 与T96类似
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */
func generateTrees(n int) []*TreeNode { 
        
    if n==0 { 
        
        return nil
    }
    data:=make([]int,n)
    for i:=1;i<=n;i++ { 
        
        data[i-1]=i
    }
    return generateTreesAssist(data)
}

func generateTreesAssist(data []int) []*TreeNode { 
        
    if len(data)==0 { 
        
        return []*TreeNode{ 
        nil}
    }
    ans:=[]*TreeNode{ 
        }
    for i:=0;i<len(data);i++ { 
        
        list1:=generateTreesAssist(data[:i])
        list2:=generateTreesAssist(data[i+1:])
        for ix1:=range list1 { 
        
            for ix2:=range list2 { 
        
                tmp:=&TreeNode{ 
        data[i],nil,nil}
                tmp.Left 

        标签： t236集成电路
 
锐单商城拥有海量元器件数据手册、
          IC替代型号，打造
          电子元器件IC百科大全！

锐单商城 - 一站式电子元器件采购平台