网站建设成都云,有域名了网站怎么做,广州哪里能看海,金溪县建设局网站文章目录 二叉树基础二叉树种类满二叉树完全二叉树二叉搜索树平衡二叉搜索树 二叉树的存储方式链式存储顺序存储 二叉树的遍历方式二叉树的定义 二叉树的递归遍历144.二叉树的前序遍历代码#xff1a; 145.二叉树的后序遍历代码#xff1a; 94. 二叉树的中序遍历代码 二叉树的… 文章目录 二叉树基础二叉树种类满二叉树完全二叉树二叉搜索树平衡二叉搜索树 二叉树的存储方式链式存储顺序存储 二叉树的遍历方式二叉树的定义 二叉树的递归遍历144.二叉树的前序遍历代码 145.二叉树的后序遍历代码 94. 二叉树的中序遍历代码 二叉树的迭代遍历前序遍历迭代法-中左右-中右左模拟出入栈代码 后序遍历迭代法思路代码 中序遍历迭代法代码 二叉树的统一迭代法-画图理解增加熟练前序遍历写法-右左中反过来中序遍历写法-右中左 后序遍历-中右左 二叉树基础
二叉树种类
满二叉树 完全二叉树 二叉搜索树 平衡二叉搜索树 二叉树的存储方式
链式存储 顺序存储 二叉树的遍历方式
二叉树主要有两种遍历方式
深度优先遍历先往深走遇到叶子节点再往回走。广度优先遍历一层一层的去遍历。
这两种遍历是图论中最基本的两种遍历方式后面在介绍图论的时候 还会介绍到。
那么从深度优先遍历和广度优先遍历进一步拓展才有如下遍历方式
深度优先遍历 前序遍历递归法迭代法中序遍历递归法迭代法后序遍历递归法迭代法 广度优先遍历 层次遍历迭代法 在深度优先遍历中有三个顺序前中后序遍历 有同学总分不清这三个顺序经常搞混我这里教大家一个技巧。
这里前中后其实指的就是中间节点的遍历顺序只要大家记住 前中后序指的就是中间节点的位置就可以了。
看如下中间节点的顺序就可以发现中间节点的顺序就是所谓的遍历方式
前序遍历中左右中序遍历左中右后序遍历左右中
二叉树的定义
public class TreeNode {int val;TreeNode left;TreeNode right;TreeNode() {}TreeNode(int val) { this.val val; }TreeNode(int val, TreeNode left, TreeNode right) {this.val val;this.left left;this.right right;}
}二叉树的递归遍历 144.二叉树的前序遍历
前序遍历中左右
代码
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val val;* this.left left;* this.right right;* }* }*/
class Solution {public ListInteger preorderTraversal(TreeNode root) {ListInteger result new ArrayList();//结果数组preorder(root,result);//开始从根节点遍历return result;}public void preorder(TreeNode root,ListInteger res){if(rootnull){return; //直接返回}res.add(root.val);//添加根节点preorder(root.left,res);preorder(root.right,res);}
}145.二叉树的后序遍历
左右中
代码
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val val;* this.left left;* this.right right;* }* }*/
class Solution {public ListInteger postorderTraversal(TreeNode root) {ListInteger res new ArrayList();postOrder(root,res);return res;}public void postOrder(TreeNode root,ListInteger res){if(rootnull){return;}postOrder(root.left,res);postOrder(root.right,res);res.add(root.val);}
}94. 二叉树的中序遍历
左中右
代码
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val val;* this.left left;* this.right right;* }* }*/
class Solution {public ListInteger inorderTraversal(TreeNode root) {ListInteger res new ArrayList();inOrder(root,res);return res;}public void inOrder(TreeNode root,ListInteger res){if(rootnull){return;}inOrder(root.left,res);res.add(root.val);inOrder(root.right,res);}
}二叉树的迭代遍历
前序遍历迭代法-中左右-中右左模拟出入栈
我们先看一下前序遍历。
前序遍历是中左右每次先处理的是中间节点 那么先将根节点放入栈中 然后先将右孩子加入栈再加入左孩子。
为什么要先加入 右孩子再加入左孩子呢 因为这样出栈的时候才是中左右的顺序。
动画如下
代码
// 前序遍历顺序中-左-右入栈顺序中-右-左
class Solution {public ListInteger preorderTraversal(TreeNode root) {ListInteger resnew ArrayList();if(rootnull){return res;}StackTreeNode stacknew Stack();stack.push(root);//加入根节点while(!stack.isEmpty()){//中TreeNode nodestack.pop();//弹出根节点res.add(node.val);//储存根节点的数值//右if(node.right!null){stack.push(node.right);}//左if(node.left!null){stack.push(node.left);}}return res;}
}后序遍历迭代法
思路
前序遍历的数组储存是中左右那么把函数翻转则变成数组储存是中右左再将数组进行翻转则变成左右中。
代码
// 后序遍历顺序 左-右-中 入栈顺序中-左-右 出栈顺序中-右-左 最后翻转结果
class Solution {public ListInteger postorderTraversal(TreeNode root) {ListInteger res new ArrayList();StackTreeNode stacknew Stack();if(rootnull){return res;}stack.push(root);while(!stack.isEmpty()){TreeNode node stack.pop();res.add(node.val);if(node.left!null){stack.push(node.left);}if(node.right!null){stack.push(node.right);}}Collections.reverse(res);//反转数组return res;}
}中序遍历迭代法
为了解释清楚我说明一下 刚刚在迭代的过程中其实我们有两个操作
处理将元素放进result数组中访问遍历节点 分析一下为什么刚刚写的前序遍历的代码不能和中序遍历通用呢因为前序遍历的顺序是中左右先访问的元素是中间节点要处理的元素也是中间节点所以刚刚才能写出相对简洁的代码因为要访问的元素和要处理的元素顺序是一致的都是中间节点。
那么再看看中序遍历中序遍历是左中右先访问的是二叉树顶部的节点然后一层一层向下访问直到到达树左面的最底部再开始处理节点也就是在把节点的数值放进result数组中这就造成了处理顺序和访问顺序是不一致的。
那么在使用迭代法写中序遍历就需要借用指针的遍历来帮助访问节点栈则用来处理节点上的元素。
动画如下
代码
// 中序遍历顺序: 左-中-右 入栈顺序 左-右
class Solution {public ListInteger inorderTraversal(TreeNode root) {ListInteger result new ArrayList();if (root null){return result;}StackTreeNode stack new Stack();TreeNode cur root;while (cur ! null || !stack.isEmpty()){if (cur ! null){stack.push(cur);cur cur.left;}else{cur stack.pop();result.add(cur.val);cur cur.right;}}return result;}
}二叉树的统一迭代法-画图理解增加熟练 前序遍历写法-右左中反过来
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val val;* this.left left;* this.right right;* }* }*/
class Solution {public ListInteger preorderTraversal(TreeNode root) {ListInteger res new LinkedList();StackTreeNode stack new Stack();if(root!null){stack.push(root);}while(!stack.isEmpty()){TreeNode nodestack.peek();//栈中的第一个节点if(node!null){stack.pop();//弹出避免重复下面再将右左中节点添加到栈中if(node.right!null){//添加右节点空节点不入栈stack.push(node.right); }if(node.left!null){//添加左节点空节点不入栈stack.push(node.left);}stack.push(node);//添加中节点stack.push(null);//中节点还没有处理添加空节点null做标记}else{stack.pop();//弹出nullnodestack.peek();//重新取出栈中元素stack.pop();//取出后再弹出res.add(node.val);}}return res;}
}中序遍历写法-右中左
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val val;* this.left left;* this.right right;* }* }*/
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val val;* this.left left;* this.right right;* }* }*/
class Solution {public ListInteger inorderTraversal(TreeNode root) {ListInteger res new ArrayList();StackTreeNode stack new Stack();if(root!null){//先放入根节点stack.push(root);}while(!stack.isEmpty()){TreeNode node stack.peek();//查找第一个结点if(node!null){stack.pop();//弹出重复节点按顺序放入右中左if(node.right!null){stack.push(node.right);}stack.push(node);stack.push(null);if(node.left!null){stack.push(node.left);}}else{stack.pop();node stack.peek();stack.pop();res.add(node.val);}}return res;}
}后序遍历-中右左
class Solution {public ListInteger postorderTraversal(TreeNode root) {ListInteger res new ArrayList();StackTreeNode stack new Stack();if(root!null){//先放入根节点stack.push(root);}while(!stack.isEmpty()){TreeNode node stack.peek();//查找第一个结点if(node!null){stack.pop();//弹出重复节点按顺序放入中右左stack.push(node);stack.push(null);if(node.right!null){stack.push(node.right);}if(node.left!null){stack.push(node.left);}}else{stack.pop();node stack.peek();stack.pop();res.add(node.val);}}return res;}
}
