【算法题二叉树面试题
树
算法题二叉树部分面试题,在面试前是很有必要针对性的刷一些题,很多朋友的实战能力很强,但是理论比较薄弱,面试前不做准备是很吃亏的。算法题作为面试的核心环节,是代码编写能力的重要体现。
本章节主要对树的常见面试题进行总结。
前序遍历
题目:144. 二叉树的前序遍历 。核心思想:栈、根左右
代码如下:
package main import "fmt" type TreeNode struct { Val int Left *TreeNode Right *TreeNode } func preorderTraversal(root *TreeNode) []int { if root == nil { return []int{} } stack := []*TreeNode{root} ans := []int{} for len(stack) > 0 { root = stack[len(stack)-1] ans = append(ans, root.Val) stack = stack[:len(stack)-1] if root.Right != nil { stack = append(stack, root.Right) } if root.Left != nil { stack = append(stack, root.Left) } } return ans } func main() { var root *TreeNode = &TreeNode{ Val: 1, Left: &TreeNode{ Val: 2, Left: nil, Right: nil, }, Right: &TreeNode{ Val: 3, Left: nil, Right: nil, }, } fmt.Println("Hello World!", preorderTraversal(root)) }
中序遍历
题目94. 二叉树的中序遍历。 核心思想:栈,左根右
package main import "fmt" type TreeNode struct { Val int Left *TreeNode Right *TreeNode } func inorderTraversal(root *TreeNode) []int { stack := []*TreeNode{} ans := []int{} 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] ans = append(ans, root.Val) if root.Right != nil { root = root.Right } else { root = nil } } return ans } func main() { var root *TreeNode = &TreeNode{ Val: 1, Left: &TreeNode{ Val: 2, Left: nil, Right: nil, }, Right: &TreeNode{ Val: 3, Left: nil, Right: nil, }, } fmt.Println(inorderTraversal(root)) }
后序遍历
题目145. 二叉树的后序遍历。 核心思想:栈,左右根
package main import "fmt" type TreeNode struct { Val int Left *TreeNode Right *TreeNode } func postorderTraversal(root *TreeNode) []int { stack := []*TreeNode{} ans := []int{} var pre *TreeNode = nil 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] if root.Right == nil || root.Right == pre { ans = append(ans, root.Val) pre = root root = nil } else { stack = append(stack, root) root = root.Right } } return ans } func main() { var root *TreeNode = &TreeNode{ Val: 1, Left: &TreeNode{ Val: 2, Left: nil, Right: nil, }, Right: &TreeNode{ Val: 3, Left: nil, Right: nil, }, } fmt.Println(postorderTraversal(root)) }
按照层遍历
按层遍历使用队列就可以来解决问题。
题目102. 二叉树的层序遍历。 给你二叉树的根节点 root ,返回其节点值的 层序遍历 。 (即逐层地,从左到右访问所有节点)。
package main import "fmt" type TreeNode struct { Val int Left *TreeNode Right *TreeNode } func levelOrder(root *TreeNode) [][]int { if root == nil { return [][]int{} } stack := []*TreeNode{root} ans := [][]int{} for len(stack) > 0 { temp := []int{} size := len(stack) for i := 0; i < size; i++ { node := stack[0] stack = stack[1:] temp = append(temp, node.Val) if node.Left != nil { stack = append(stack, node.Left) } if node.Right != nil { stack = append(stack, node.Right) } } ans = append(ans, temp) } return ans } func main() { var root *TreeNode = &TreeNode{ Val: 1, Left: &TreeNode{ Val: 2, Left: nil, Right: nil, }, Right: &TreeNode{ Val: 3, Left: nil, Right: nil, }, } fmt.Println(levelOrder(root)) }
相似题目:
题目:103. 二叉树的锯齿形层序遍历
题目:107. 二叉树的层序遍历 II
题目:199. 二叉树的右视图
题目:二叉树的左视图
题目:LCR 144. 翻转二叉树。 这里也可以使用按照其他形式进行遍历,遍历出来所有节点后,对节点进行反转即可。
题目:958. 二叉树的完全性检验。 核心:还是按照层遍历,判断连续的中间是否空值存在。
isFindNil := false for i:=0; i b { return a } return b } func maxDepth(root *TreeNode) int { if root == nil { return 0 } lh := maxDepth(root.Left) rh := maxDepth(root.Right) return max(lh, rh) + 1 }
二叉树的所有路径
题目:257. 二叉树的所有路径 给你一个二叉树的根节点 root ,按 任意顺序 ,返回所有从根节点到叶子节点的路径。
核心点:就是递归,注意数字转化为字符串的方法 strconv.Itoa()
func binaryTreePaths(root *TreeNode) []string { ans := []string{} var dfs func(root *TreeNode, path string) dfs = func(root *TreeNode, path string) { if root.Left == nil && root.Right == nil { path = path + strconv.Itoa(root.Val) ans = append(ans, path) return } path = path + strconv.Itoa(root.Val)+ "->" if root.Left != nil { dfs(root.Left, path) } if root.Right != nil { dfs(root.Right, path) } } dfs(root, "") return ans; }
平衡二叉树
题目:110. 平衡二叉树
平衡二叉树: 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。核心:还是递归,用-1 作为不平衡的特殊值,也可以结束循环
func max(a int, b int) int { if a > b { return a } return b } func abs(a int, b int) int { if a - b > 0 { return a - b } return b - a } func isBalanced(root *TreeNode) bool { var height func(root *TreeNode) int height = func(root *TreeNode) int { if root == nil { return 0 } lh := height(root.Left) rh := height(root.Right) if lh == -1 || rh == -1 || abs(lh, rh) > 1 { return -1 } return max(lh, rh) + 1 } if (height(root)>-1){ return true } return false }
二叉树的直径
题目:543. 二叉树的直径 二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。核心:递归分别计算左右两个节点的长度。
func max(a, b int) int{ if a > b { return a } return b } func diameterOfBinaryTree(root *TreeNode) int { maxDepth := 0 var dfs func(root *TreeNode) int dfs = func(root *TreeNode) int { if root == nil { return 0 } lh := dfs(root.Left) rh := dfs(root.Right) depth := max(lh, rh) + 1 maxDepth = max(maxDepth, lh + rh + 1) return depth } dfs(root) return maxDepth-1 }
相似题目: 题目:124. 二叉树中的最大路径和。核心:递归返回的是到此节点的最大值是多少。
func max(a, b int) int { if a > b { return a } return b } func maxPathSum(root *TreeNode) int { if root == nil{ return 0 } maxGain := ^int(^uint(0) >> 1) var dfs func(root *TreeNode) int dfs = func(root *TreeNode) int { if root == nil { return 0 } lh := max(dfs(root.Left), 0) rh := max(dfs(root.Right),0) maxGain = max(maxGain, lh + rh + root.Val) return max(lh, rh) + root.Val } dfs(root) return maxGain }
二叉树的最近公共祖先
题目:236. 二叉树的最近公共祖先。给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
核心:递归, 返回 是否包含 其中的一个节点。 赋值的条件是 左右都包含,或者是当前为节点值为其中一个,左右包含一个。
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode { var dfs func(root *TreeNode, p, q *TreeNode) bool var ans *TreeNode = nil dfs = func(root, p, q *TreeNode) bool{ if root == nil { return false } lh := dfs(root.Left, p, q) rh := dfs(root.Right, p, q) if (lh && rh) || ( (root.Val == p.Val || root.Val == q.Val) && (lh || rh) ) { ans = root return true } return lh || rh || root.Val == p.Val || root.Val == q.Val } dfs(root, p, q) return ans }
路径类型题目
核心: 这种类型的题目还是递归,将路径记录下来。
func pathSum(root *TreeNode, targetSum int) [][]int { ans := [][]int{} var dfs func(root *TreeNode, path []int, sum int) dfs = func(root *TreeNode, path []int, sum int) { if root.Left == nil && root.Right == nil { if sum + root.Val == targetSum { path = append(path, root.Val) ans = append(ans, append([]int(nil), path...)) return } } path = append(path, root.Val) if root.Left != nil { dfs(root.Left, path, sum + root.Val) } if root.Right != nil { dfs(root.Right, path, sum + root.Val) } } dfs(root, []int{}, 0) return ans }
func sumNumbers(root *TreeNode) int { total := 0 var dfs func(root *TreeNode, sum int) dfs = func(root *TreeNode, sum int) { if root.Left == nil && root.Right == nil { total += root.Val + sum * 10 } if root.Left != nil { dfs(root.Left, root.Val + sum * 10) } if root.Right != nil { dfs(root.Right, root.Val + sum * 10) } } dfs(root, 0) return total }