广度优先搜索dfs

layout: post title: “DFS-广度优先搜索” subtitle: “” date: 2019-09-09 author: “CHuiL” header-img: “img/algorithm-bg.png” tags:

算法

103. Binary Tree Zigzag Level Order Traversal

题目

Given a binary tree, return the zigzag level order traversal of its nodes’ values. (ie, from left to right, then right to left for the next level and alternate between).

For example: Given binary tree [3,9,20,null,null,15,7],

大意

一层一层的遍历树节点，要求按z字形输出

例子

题解

两个队列来交替存储，判断一层结束后输出，输出的时候根据flag来决定是正向还是反向；

代码

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func zigzagLevelOrder(root *TreeNode) [][]int {
    res := make([][]int,0)
    if root==nil{
        return res
    }
    
    flag := 1
    queue := make([]*TreeNode,0)
    queue_swap := make([]*TreeNode,0)
    
    temp_res := make([]int,0)
    queue = append(queue,root)
    for len(queue)!=0{
        var r *TreeNode
        r = queue[0]
        queue = queue[1:]

        if r.Left!=nil{
            queue_swap = append(queue_swap,r.Left)
        }
        if r.Right!=nil{
            queue_swap = append(queue_swap,r.Right)
        }
        
        temp_res = append(temp_res,r.Val)
        
        if len(queue)==0{
            queue = queue_swap
            queue_swap = make([]*TreeNode,0)
            
            if flag==-1{
                i,j := 0,len(temp_res)-1
                for i<=j{
                    temp_res[i],temp_res[j] = temp_res[j],temp_res[i]
                    i++
                    j--
                }
            }
            
            res = append(res,temp_res)
            temp_res = make([]int,0)
            flag = flag*-1
        }
        
    }
    return res
    
}

102. Binary Tree Level Order Traversal

与103相似，只是不要求z形输出了

127. Word Ladder

Given two words (beginWord and endWord), and a dictionary’s word list, find the length of shortest transformation sequence from beginWord to endWord, such that:

Only one letter can be changed at a time. Each transformed word must exist in the word list. Note that beginWord is not a transformed word.

Note:

Return 0 if there is no such transformation sequence.
All words have the same length.
All words contain only lowercase alphabetic characters.
You may assume no duplicates in the word list.
You may assume beginWord and endWord are non-empty and are not the same.

代码

func ladderLength(beginWord string, endWord string, wordList []string) int {
	if wordList==nil{
		return 0
	}

	if len(wordList)==0{
		return 0
	}

	queue := make([]string,0)
	queue = append(queue,beginWord)
	queue_swap := make([]string,0)
	count:=0
	for len(queue)!=0{
		str := queue[0]
		queue = queue[1:]

		if str==endWord{
			count++
			return count
		}

		i:=0
		for ;i<len(wordList);{
			if NextWord(str,wordList[i]) {
				queue_swap = append(queue_swap,wordList[i])
				wordList = append(wordList[:i],wordList[i+1:]...)
			}else{
				i++
			}
		}

		if len(queue)==0{
			queue = queue_swap
			queue_swap = make([]string,0)
			count++
		}
	}
	return 0

}

func NextWord(pre,next string)bool{
	count:=0
	for i,_ := range next{
		if next[i]==pre[i]{
			count++
		}
	}
	if count==len(pre)-1{
		return true
	}
	return false
}