首页>内容详情

【算题题】二叉树面试题

大熊•2023-10-12 23:03:39

树

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

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

前序遍历

代码如下:

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<len(stack); i++ {
    if stack[i] != nil && isFindNil {
        return false
    }
    if stack[i] == nil {
        isFindNil = true
    }
}
return true

题目：1302. 层数最深叶子节点的和。核心：还是按层遍历。记录每层的最大和。

二叉树的最大深度

104. 二叉树的最大深度

核心：递归

func max(a int, b int) int {
    if a > 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. 求根节点到叶节点数字之和

上一篇：【数据库面试题】常见数据库基础面试题

下一篇：【面试题】回文类型题目