Skip to content

Latest commit

 

History

History
710 lines (584 loc) · 14.5 KB

二叉树全集.md

File metadata and controls

710 lines (584 loc) · 14.5 KB

二叉树全集

236. 二叉树的最近公共祖先

func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
   if root==nil{
   	 return nil
   }
   if p ==root || q==root{
   	return root
   }
   left :=lowestCommonAncestor(root.Left,p,q)
   right :=lowestCommonAncestor(root.Right,p,q)
   if left!=nil&&right!=nil{
   	return root
   }
 
   if left==nil{
   return right
   }
   return left
}

144. 二叉树的前序遍历

// 递归
var result []int
func preorderTraversal(root *TreeNode) []int {
     result =[]int{}
     r :=helper(root)
     return r
}


func helper(root *TreeNode)[]int{
     if root == nil{
          return []int{}
      }
      result=append(result,root.Val)
      helper(root.Left)
      helper(root.Right)
      return result

}
// 前序迭代
func preorderTraversal(root *TreeNode) (vals []int) {
    stack := []*TreeNode{}
    node := root
    for node != nil || len(stack) > 0 {
        for node != nil {
            vals = append(vals, node.Val)
            stack = append(stack, node)
            node = node.Left
        }
        node = stack[len(stack)-1].Right
        stack = stack[:len(stack)-1]
    }
    return
}

// 中序迭代
func inorderTraversal(root *TreeNode) (res []int) {
	stack := []*TreeNode{}
	for root != nil || len(stack) > 0 {
		for root != nil {
			stack = append(stack, root)
			root = root.Left
		}
		root = stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		res = append(res, root.Val)
		root = root.Right
	}
	return
}

// 后序迭代

func postorderTraversal(root *TreeNode) (res []int) {
    stk := []*TreeNode{}
    var prev *TreeNode
    for root != nil || len(stk) > 0 {
        for root != nil {
            stk = append(stk, root)
            root = root.Left
        }
        root = stk[len(stk)-1]
        stk = stk[:len(stk)-1]
        if root.Right == nil || root.Right == prev {
            res = append(res, root.Val)
            prev = root
            root = nil
        } else {
            stk = append(stk, root)
            root = root.Right
        }
    }
    return
}

102. 二叉树的层序遍历

func levelOrder(root *TreeNode) [][]int {
    if root==nil{                         //为空则返回nil   
        return [][]int{}
    }
    ret:=[][]int{}       //用来最后的结果
    result:=[]int{}    //用来存储每一层的值，到新的一层时需要进行清空
    num:=[]*TreeNode{}     //树的节点队列
    num=append(num,root)
    for len(num)!=0{
        length:=len(num)     //每次从队列中取出length个节点，加入result
        result=[]int{}    //清空当前层的所有结点的值
        for i:=0;i<length;i++{
            result=append(result,num[i].Val)    //相同一层的节点同时加入result
            if num[i].Left!=nil{
                num=append(num,num[i].Left)     //左子树入队
            }
            if num[i].Right!=nil{
                num=append(num,num[i].Right)    //右子树入队
            }
        }
        ret =append(ret,result)       //每一层的result都要加入ret,
        num=num[length:]    //已经被返回过的结点需要出队
    }
    return ret
}

429. N 叉树的层序遍历

func levelOrder(root *Node) [][]int {
	if root==nil{
		return [][]int{}
	}
	queue :=[]*Node{}
	result :=[][]int{}
	queue=append(queue,root)

	for len(queue)>0{
		tmp:=[]int{}
		count :=len(queue)
		for i:=0;i<count;i++{
			
			tmp=append(tmp,queue[i].Val)
			for _,v:= range queue[i].Children{
				queue=append(queue,v)
			}
		}
        result=append(result,tmp)
		queue=queue[count:]
		
	}
	return  result

}

116. 填充每个节点的下一个右侧节点指针

func connect(root *Node) *Node {
    if root == nil{
        return nil
    }
	queueN :=[]*Node{}
    queueN =append(queueN,root)
    for len(queueN)>0{
        length :=len(queueN)
        for i:=0;i<length;i++{
        if i+1 <length{
             queueN[i].Next=queueN[i+1]
        } else {
            queueN[i].Next=nil
        }
        if queueN[i].Left !=nil{
            queueN =append(queueN,queueN[i].Left)
        }
        if queueN[i].Right !=nil{
            queueN = append(queueN,queueN[i].Right)
        }
        }

    queueN=queueN[length:]
    }
    return root
}

101. 对称二叉树

func isSymmetric(root *TreeNode) bool {
	if root == nil{
		return true
	}

	return helper(root.Left,root.Right)
}

func helper(left,right *TreeNode) bool {

	if left == nil || right == nil{
		return left == right
	}

	if left.Val != right.Val{
		return false
	}

	return helper(left.Left,right.Right)&&helper(left.Right,right.Left)

}

111. 二叉树的最小深度

// 非递归
func minDepth(root *TreeNode) int {
	 queueNode :=[]*TreeNode{}
	 queueIndex :=[]int{}
	if root == nil{
		return 0
	}
	if root.Left==nil && root.Right == nil{
		return 1
	}
	queueNode = append(queueNode,root)
	queueIndex = append(queueIndex,1)
	for i := 0; i <len(queueNode) ; i++ {
             node :=queueNode[i]
             depth :=queueIndex[i]
             if node.Left==nil&&node.Right==nil{
             	return depth
			 }
			 if node.Left !=nil{
			 	queueNode = append(queueNode,node.Left)
			 	queueIndex = append(queueIndex,depth+1)
			 }
			 if node.Right !=nil{
			 	queueNode = append(queueNode,node.Right)
				 queueIndex = append(queueIndex,depth+1)
			 }
	}
return 0
}

// 递归
func minDepth(root *TreeNode) int {
         if root == nil{
         	return 0
		 }
		 if root.Left==nil && root.Right == nil{
		 	return 1
		 }

		 left :=minDepth(root.Left)
		 right :=minDepth(root.Right)
		 if left == 0{
		 	return right+1
		 }
		 if right == 0{
		 	return left+1
		 }


		 return min(left,right)+1
}
func min(a,b int)int  {
	if a<=b{
		return a
	}else {
		return b
	}
}

110. 平衡二叉树

func isBalanced(root *TreeNode) bool {
      if root==nil{
          return true
      }

      return isBalanced(root.Left)&&isBalanced(root.Right)&&(abs(depth(root.Left),depth(root.Right))<=1)
}



func depth(root *TreeNode)int{
    if root == nil{
        return 0
    }

    return max(depth(root.Left),depth(root.Right))+1
}


func max(a,b int)int{
    if a>=b{
        return a
    }
    return b
}

func abs(a,b int)int{
    if a>=b{
        return a-b
    }

    return b-a
}

257. 二叉树的所有路径

var result []string
func binaryTreePaths(root *TreeNode) []string {
       result =[]string{}
       reverse(root,"")
       return result
}

func reverse(root *TreeNode,path string){
    if root==nil{
        return
    }
    pathT :=path
    pathT = pathT+strconv.Itoa(root.Val)
    if root.Left==nil && root.Right==nil{
        result=append(result,pathT)
        
    }else{
        pathT=pathT+"->"
    reverse(root.Left,pathT)
    reverse(root.Right,pathT)
    }
}

404. 左叶子之和

func sumOfLeftLeaves(root *TreeNode) int {
     r :=helper(root,0)
     return r
}


func helper(root *TreeNode,sum int) int{
    if root==nil{
        return 0
    }
    tmp:=0
    if root.Left !=nil&&root.Left.Left==nil&&root.Left.Right==nil{
         tmp=root.Left.Val
    }
    l :=helper(root.Left,sum)
    r :=helper(root.Right,sum)
    return l+r+tmp
}

1022. 从根到叶的二进制数之和

func sumRootToLeaf(root *TreeNode) int {
  
  r:=helper(root,0)
  return r
}

func helper(root *TreeNode,sum int)int{
    if root ==nil{
        return 0
    }
    sum =sum*2+root.Val // 10进制类似
    if root.Left==nil&&root.Right==nil{
        return sum
    }

    return helper(root.Left,sum)+helper(root.Right,sum)
}

113. 路径总和 II

var result [][]int
func pathSum(root *TreeNode, targetSum int) [][]int {
    if root == nil {
        return [][]int{}
    }
    result = [][]int{}
    path :=[]int{}
    reverse(root,targetSum,path)

    return result

}

func reverse(root *TreeNode, targetSum int,path []int){
    if root == nil{
        return
    }
    path = append(path,root.Val)
    targetSum = targetSum-root.Val
    if targetSum == 0 && root.Left==nil && root.Right==nil{
        tmp :=make([]int,len(path))
        copy(tmp,path)
        result =append(result,tmp)
        return 
    }
    reverse(root.Left,targetSum,path)
    reverse(root.Right,targetSum,path)
}

98. 验证二叉搜索树

二叉搜索树 中序遍历很好用

func isValidBST(root *TreeNode) bool {
 
   return helper(root,math.MinInt64,math.MaxInt64)

}
func helper(root *TreeNode,min ,max int) bool {
    if root == nil{
        return true
    }
    if root.Val <=min{
        return false
    }
    if root.Val >=max{
        return false
    }
    return helper(root.Left,min,root.Val) && helper(root.Right,root.Val,max)
}

1008. 前序遍历构造二叉搜索树

1.把前序数组排序，构成中序遍历，然后利用前序和中序

func bstFromPreorder(preorder []int) *TreeNode {
  	old :=make([]int,len(preorder))
	copy(old,preorder)
    sort.Ints(preorder)
    root :=buildTree(old,preorder)
    return root
}



func buildTree(preorder []int, inorder []int) *TreeNode {
   if len(inorder)==0 || len(preorder)==0{
        return nil
    }

    rootVal :=preorder[0]
     
    rootIndex :=0

      for i,v :=range inorder{
          if v == rootVal{
              rootIndex = i
          }
      }
      leftArr :=inorder[:rootIndex]
      rightArr :=inorder[rootIndex+1:]
      postLeft :=preorder[1:len(leftArr)+1]
      postRight :=preorder[len(leftArr)+1:len(preorder)]
      rootNode :=&TreeNode{
          Val:rootVal,
      }
     rootNode.Left = buildTree(postLeft,leftArr)
     rootNode.Right = buildTree(postRight,rightArr)

     return rootNode
}

2.利用二叉搜索树插入操作

func bstFromPreorder(preorder []int) *TreeNode {
	if len(preorder)==0{
		return nil
	}
	if len(preorder)==1{
		return &TreeNode{
			Val:   preorder[0],
			Left:  nil,
			Right: nil,
		}
	}
              root :=TreeNode{
				  Val:   preorder[0],
				  Left:  nil,
				  Right: nil,
			  }
	for _,v:=range preorder{
		insertIntoBST(&root,v)
	}
			  return &root
}

func insertIntoBST(root *TreeNode, val int) *TreeNode {
	if root==nil {
		return &TreeNode{
			Val:   val,
			Left:  nil,
			Right: nil,
		}
	}
	if root.Val > val{
		left:=insertIntoBST(root.Left,val)
		root.Left = left
	}
	if root.Val < val{
		right :=insertIntoBST(root.Right,val)
		root.Right = right
	}
	return root
}

701. 二叉搜索树中的插入操作

func insertIntoBST(root *TreeNode, val int) *TreeNode {
           if root==nil{
           	 return &TreeNode{
				 Val:   val,
				 Left:  nil,
				 Right: nil,
			 }
		   }
		   if root.Val > val{
		   	 left:=insertIntoBST(root.Left,val)
		   	 root.Left = left
		   }
	if root.Val < val{
		right :=insertIntoBST(root.Right,val)
		root.Right = right
	}
	return root
}

450. 删除二叉搜索树中的节点

func deleteNode(root *TreeNode, key int) *TreeNode {
	  if root == nil{
	  	return nil
	  }
	  if root.Val==key{

			if root.Left==nil{
				return root.Right
			}
		  if root.Right==nil{
			  return root.Left
		  }
		  minNode :=getMinNode(root.Right)
		  root.Val = minNode.Val
		  root.Right=deleteNode(root.Right,minNode.Val)
	  }
	  if root.Val < key{
	  	right :=deleteNode(root.Right,key)
	  	root.Right = right
	  }
	if root.Val > key{
		left :=deleteNode(root.Left,key)
		root.Left = left
	}
	return root
}

func getMinNode(root *TreeNode)  *TreeNode{
	for root.Left!=nil{
		root=root.Left
	}
	return root
}

669. 修剪二叉搜索树

func trimBST(root *TreeNode, low int, high int) *TreeNode {
     if root == nil{
         return nil
     }

     if root.Val>= low && root.Val <= high{
         root.Left = trimBST(root.Left,low,high)
         root.Right = trimBST(root.Right,low,high)

     }else if root.Val < low{
         root = root.Right
         root = trimBST(root,low,high)

     }else {
         root = root.Left
         root = trimBST(root,low,high)
     }
     return root
}

108. 将有序数组转换为二叉搜索树

func sortedArrayToBST(nums []int) *TreeNode {
   
    return helper(nums,0,len(nums)-1)
}


func helper(nums []int,left,right int)*TreeNode{
    if left > right {
        return nil
    }
    midV :=left +(right-left)/2
    root :=&TreeNode{
        Val:nums[midV],
        Left:helper(nums,left,midV-1),
        Right:helper(nums,midV+1,right),
    }

    return root
}

235. 二叉搜索树的最近公共祖先

func lowestCommonAncestor(root, p, q *TreeNode) (ancestor *TreeNode) {
    ancestor = root
    for {
        if p.Val < ancestor.Val && q.Val < ancestor.Val {
            ancestor = ancestor.Left
        } else if p.Val > ancestor.Val && q.Val > ancestor.Val {
            ancestor = ancestor.Right
        } else {
            return
        }
    }
}

538. 把二叉搜索树转换为累加树

var sum int
func convertBST(root *TreeNode) *TreeNode {
     sum =0
     helper(root)
     return root
}

func helper(root *TreeNode){
    if root == nil {
        return
    }
  
    helper(root.Right)
    sum+=root.Val
    root.Val = sum
    helper(root.Left)
}

补充

297. 二叉树的序列化与反序列化