目录1、二叉树介绍【1】核心概念【2】关键特性2、算法题【1】二叉树的前序遍历【2】二叉树的后序遍历【3】二叉树的中序遍历1、二叉树介绍【1】核心概念结构含义节点结构二叉树由节点组成 每个节点包含一个数据元素和最多两个子节点左子节点和右子节点根节点树的顶部节点称为根节点是访问整个树的起点叶节点没有子节点的节点成为叶节点子树每个节点及其后代构成一个子树【2】关键特性特性含义最大子节点数每个节点最多有两个子节点遍历方式前序遍历根-左-右中序遍历左-根-右后序遍历左-右-根层次遍历按层从做到右常见类型二叉搜索树BST左子树所有节点值小于根节点右子树所有节点值大于根节点用于高效搜索平衡二叉树AVL树自动保持树的高度平衡确保操作效率堆用于优先队列如最大堆和最小堆2、算法题【1】二叉树的前序遍历LeetCode第144题题目如下给你二叉树的根节点 root 返回它节点值的 前序 遍历。示例 1输入root [1,null,2,3]输出[1,2,3]示例 2输入root [1,2,3,4,5,null,8,null,null,6,7,9]输出[1,2,4,5,6,7,3,8,9]示例 3输入root []输出[]示例 4输入root [1]输出[1]提示树中节点数目在范围 [0, 100] 内-100 Node.val 100代码示例// 节点的结构体有3个对象// 1、节点值// 2、左节点指针// 3、右节点指针typeTreeNodestruct{ValintLeft*TreeNode Right*TreeNode}//前序遍历解法//根左右//递归解法、遍历解法// 递归解法funcPreorderTraversal(root*TreeNode)[]int{ifrootnil{return[]int{}}//返回值varres[]int//定义递归函数变量vartraversalfunc(node*TreeNode)//实现递归函数traversalfunc(node*TreeNode){ifnodenil{return}resappend(res,node.Val)traversal(node.Left)traversal(node.Right)}//调用递归函数traversal(root)returnres}// 迭代解法funcpreOrderTraversal2(root*TreeNode)[]int{//根节点为空直接返回ifrootnil{return[]int{}}//定义返回值varresult[]int//根节点入栈stack:[]*TreeNode{root}//循环遍历节点弹出栈forlen(stack)0{//弹出栈顶节点node:stack[len(stack)-1]resultappend(result,node.Val)//删除栈中栈顶节点stackstack[:len(stack)-1]//由于栈是先进后出所以右节点先入栈左节点再入栈ifnode.Right!nil{stackappend(stack,node.Right)}ifnode.Left!nil{stackappend(stack,node.Left)}}//返回响应值returnresult}【2】二叉树的后序遍历LeetCode第145题题目如下给你一棵二叉树的根节点 root 返回其节点值的 后序遍历 。示例 1输入root [1,null,2,3]输出[3,2,1]示例 2输入root [1,2,3,4,5,null,8,null,null,6,7,9]输出[4,6,7,5,2,9,8,3,1]示例 3输入root []输出[]示例 4输入root [1]输出[1]提示树中节点的数目在范围 [0, 100] 内-100 Node.val 100代码示例/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */funcpostorderTraversal(root*TreeNode)[]int{//递归终止条件空节点返回空切片ifrootnil{return[]int{}}//递归遍历左子树left:postorderTraversal(root.Left)//递归便利右子树right:postorderTraversal(root.Right)//合并结果//先拼接左右子树结果result:append(left,right...)//最后添加当前节点值resultappend(result,root.Val)returnresult}//递归后续遍历funcpostorderTraversal1(root*TreeNode)[]int{ifrootnil{return[]int{}}stack:[]*TreeNode{root}varres[]intforlen(stack)0{//弹出栈顶节点node:stack[len(stack)-1]stackstack[:len(stack)-1]//将节点值加入结果集此时顺序为根-右-左resappend(res,node.Val)//左子节点先入栈保证下次弹出时右子节点先处理ifnode.Left!nil{stackappend(stack,node.Left)}//右子节点入栈ifnode.Right!nil{stackappend(stack,node.Right)}}//反转结果集左-右-根fori,j:0,len(res)-1;ij;i,ji1,j-1{res[i],res[j]res[j],res[i]}returnres}【3】二叉树的中序遍历LeetCode第94题题目如下给定一个二叉树的根节点 root 返回 它的 中序 遍历 。示例 1输入root [1,null,2,3]输出[1,3,2]示例 2输入root []输出[]示例 3输入root [1]输出[1]提示树中节点数目在范围 [0, 100] 内-100 Node.val 100代码示例/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } *///中序遍历//左子树-根节点-右子树// 递归解法funcInorderTraversal(root*TreeNode)[]int{//判断根节点是否为空ifrootnil{return[]int{}}//定义返回值varres[]int//定义递归函数vartraversalfunc(node*TreeNode)//实现递归函数traversalfunc(node*TreeNode){//如果节点为空直接返回ifnodenil{return}//递归左子树traversal(node.Left)//存入根节点resappend(res,node.Val)//递归右子树traversal(node.Right)}//调用递归函数traversal(root)returnres}// 迭代解法funcInorderTraversal2(root*TreeNode)[]int{//当前节点为空直接返回ifrootnil{return[]int{}}//定义返回值varres[]int//定义栈varstack[]*TreeNode//赋值当前值cur:root//当前值不为空或者栈还有数据的时候就不能结束forcur!nil||len(stack)0{//将最左边全部丢入栈中forcur!nil{stackappend(stack,cur)curcur.Left}//栈顶弹出元素node:stack[len(stack)-1]stackstack[:len(stack)-1]//返回值赋值resappend(res,node.Val)//当前节点变为右节点curnode.Right}returnres}