【算法题二叉树面试题

算法题二叉树部分面试题,在面试前是很有必要针对性的刷一些题,很多朋友的实战能力很强,但是理论比较薄弱,面试前不做准备是很吃亏的。算法题作为面试的核心环节,是代码编写能力的重要体现。

本章节主要对树的常见面试题进行总结。

二叉树.png

前序遍历

题目: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
    }

    路径类型题目

    核心: 这种类型的题目还是递归,将路径记录下来。

  • 题目:113. 路径总和 II 。给你二叉树的根节点 root 和一个整数目标和 targetSum ,找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
  • 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
    }
  • 获得所有的路径。题目:129. 求根节点到叶节点数字之和