Traversal of leetcode tree

q94 Middle order traversal of binary trees

Subject portal

Answer key

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

q144 Preorder traversal of two tree

Subject portal

Answer key

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

q145 Postorder traversal of binary trees

Subject portal

Answer key

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

q102 The level traversal of binary tree

Subject portal

Answer key

Using queue implementation ：

func levelOrder(root *TreeNode) [][]int {
    
	var res [][]int
	if root == nil {
    
		return res
	}
	//  Create a q queue , Join the nodes on the first floor every time 
	//  Join the root node for the first time 
	q := []*TreeNode{
    root}
	//  Keep joining the node on the first floor 
	for i := 0; len(q) > 0; i++ {
    
		//  Open a new floor 
		res = append(res, []int{
    })
		// p The queue is used to queue the child nodes of all nodes in the current layer , That is, the next element of the team 
		var p []*TreeNode
		//  Traverse the current layer node 
		for j := 0; j < len(q); j++ {
    
			//  Add all nodes of the current layer to res Array 
			node := q[j]
			res[i] = append(res[i], node.Val)
			//  Join the next node 
			if node.Left != nil {
    
				p = append(p, node.Left)
			}
			if node.Right != nil {
    
				p = append(p, node.Right)
			}
		}
		//  Traverse the next layer 
		q = p
	}
	return res
}

Recursive implementation ：

func levelOrder(root *TreeNode) [][]int {
    
	var res [][]int
	var dfs func(node *TreeNode, depth int)
	dfs = func(node *TreeNode, depth int) {
    
		//  Recursive export 
		if node == nil {
    
			return
		}
		//  Initialize a new layer of storage space 
		if len(res) == depth {
    
			res = append(res, []int{
    })
		}
		//  Will be the first depth The node of the layer is added to res in 
		res[depth] = append(res[depth], node.Val)
		if node.Left != nil {
    
			dfs(node.Left, depth + 1)
		}
		if node.Right != nil {
    
			dfs(node.Right, depth + 1)
		}
	}
	dfs(root, 0)
	return res
}

q110 Balanced binary trees

Subject portal

Answer key

Find the depth of the binary tree and judge whether the left and right nodes are balanced .

func isBalanced(root *TreeNode) bool {
    
	if root == nil {
    
		return true
	}
	return abs(dfs(root.Left) - dfs(root.Right)) <= 1 && isBalanced(root.Left) && isBalanced(root.Right)
}

func dfs(t *TreeNode) int {
    
	if t == nil {
    
		return 0
	}
	lChild := dfs(t.Left)
	rChild := dfs(t.Right)
	return 1 + max(lChild, rChild)
}

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

func abs(x int) int {
    
	if x < 0 {
    
		return -x
	}
	return x
}