简单二叉树的介绍
| 阿里云国内75折 回扣 微信号：monov8 |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |
1.树的结构了解
1.1概念
树是一种非线性的数据结构它是由nn>=0)个有限节点总成一个具有层次关系的集合。把它叫做树是因为它看起来像一颗倒挂的树也就是说它的根是朝上而叶子是朝下的本人而言更像一个类似于植物根它有以下的特点
有一个特殊的节点称为根节点根节点没有前驱节点
除根节点外其余节点被分成M(M>0)个互补相交的集合T1、T2........Tm,其中每个集合Ti(1<=i<=m)又是一颗与树类似的子树。每棵子树的根节点有且只有一个前驱可以有0个或者多个后继
树是递归定义的很多方法都要使用递归来解决
【注意】树形结构中子树间是没有交集的否则就不是线性结构如下图就不是树结构
1.2树的相关概念
节点的度一个节点含有子树的个数称为该节点的度如上图A的度为2B的度为2
树的度一颗树中所有节点度的最大值为树的度如上图节点的度的最大值是2所以树的度为2
叶子节点或终端节点度为0的节点称为叶节点如上图的DEFG为叶子节点或终端节点
双亲节点或父节点如一个节点含有子节点则这个节点称为其子节点的父节点如上图D的父节点是B
根节点一颗树中没有双亲节点的节点也是树开始的节点如上图的A
节点的层次从根开始定义起根为第一层根的子节点是第二层依次类推
树的高度或深度树中节点的最大层次如上图树的高度为3
以下概念了解即可
非终端节点或分支节点度不为0的节点如上图的ABC为分支节点或非终端节点
兄弟节点具有相同父节点的节点互为兄弟节点如上图的BC为兄弟节点
堂兄弟节点双亲在同一层的节点互为堂兄弟如上图的DF为堂兄弟节点
节点的祖先从根节点到该节点所经分支的所有节点如上图的D的祖先是ABD
子孙以某个节点为根的子树中任一节点都称为该节点的子孙。如上图都是A的子孙
森林由M(M>=0)棵互不相交的树组成的集合称为森林。
1.3树的表示形式了解
树结构相对于线性结构复杂很多要粗存起来就比较复杂了实际中
树有很多表示方式比如双亲表示法孩子表示法孩子双亲表示法孩子兄弟表示法等等。我们这里简单了解以下孩子兄弟表示法。
//孩子兄弟表示法
class Node {
int val;
Node firstChild; //第一个孩子
Node nextBrother; //下一个兄弟引用
}
1.4树的应用
文件系统管理目录和文件
图并不完全但足以看出是孩子兄弟表示法。
2.二叉树
2.1概念
一棵二叉树是节点的一个有限集合该集合
可以为空
或者由一个根节点加上两颗别称为左子树和右子树的二叉树组成。
从上图可以看出
二叉树不存在度大于2的节点
二叉树的子树有左右之分次序不能颠倒因此二叉树是有序树。
【注意】对于任意的二叉树都有以下几种情况复合而成的
自然阶中的“二叉树”
2.2两种特殊的二叉树
1.满二叉树一棵二叉树如果每层的节点数都达到最大值则这棵二叉树就是满二叉树。也就是说如果一颗二叉树的层数为K且节点总数是2的K次方-1则它就是满二叉树。
2.完全二叉树完全二叉树是效率很高的数据结构完全二叉树是由满二叉树而引出来的。对于深度为K的有n个节点的二叉树当且仅当其每一个节点都与深度为K的满二叉树中编号从0到n-1的节点一一对应时称之为完全二叉树。要注意满二叉树是一种特殊的完全二叉树。
错误示范只是普通的二叉树。
2.3二叉树的性质
若根节点的层数为1则一颗非空二叉树的第i层上最多有2的i-1次方个节点
若只有根节点的二叉树的深度为1则深度为K的二叉树的最大节点数是2的k次方-1
对于任何一个二叉树如果其叶节点个数为n0,度为2的非叶子节点个数为n2则有n0=n2+1;
【推导】
有n个节点的完全二叉树的深度为log以2为底n+1取上整
对于具有n个节点的完全二叉树如果从上至下从左至右的顺序对所有节点从0开始编码则对序列号为i的节点有
若i>0,双亲序号i-1)/2i=0i为根节点标号无双亲节点
若2i+1<n,左孩子序号为2i+1否则无左孩子
若2i+2<n,右孩子序号为2i+2,否则无右孩子。
1.某二叉树共有399个节点其中199个度为2的节点则该二叉树的叶子节点的个数是 200
2.在具有2n个节点的完全二叉树中叶子节点个数为 n
【解析】
3.一个具有767个节点的完全二叉树其叶子节点个数为 384
4.一颗完全二叉树的节点数是531那么这棵树的高度为 10利用公式即可得出
2.4二叉树的储存
二叉树的存储结构分为顺序储存和类似于链表的链式储存
顺序储存在以后进行讲解。
二叉树的链式储存是通过一个个的节点引用起来的常见的表示方式有二叉和三叉表示方式具体如下
//孩子表示法
class Node1 {
int val;
Node1 left;//左孩子
Node1 right;//右孩子
}
//孩子双亲表示法
class Node2 {
int val;
Node2 left;//左孩子的引用
Node2 right;//有孩子的引用
Node2 parent;//父节点的引用
}孩子双亲表示法后续在平衡树的位置介绍本文采用的是孩子表示法来构建二叉树。
2.5二叉树的基本操作
2.5.1前置说明
在学习二叉树的基本操作前需先要创建一颗二叉树然后才能学习其相关的基本操作。由于现在大家对二叉树结构掌握还不够深入为了降低大家的学习成本此处手动快速创建一棵简单的二叉树快速进入二叉树操作的学习等到二叉树结构了解差不多的时候我们发过来了解二叉树真正的创建方式
//简单创建一个二叉树
class BinaryTree {
public static class Node{
Node left;
Node right;
int val;
public Node(int val) {
this.val = val;
}
}
private Node root;
//并不是真正创建二叉树的方式但这里我们只是方便理解
public void createBinaryTree() {
Node n1 = new Node(1);
Node n2 = new Node(2);
Node n3 = new Node(3);
Node n4 = new Node(4);
Node n5 = new Node(5);
Node n6 = new Node(6);
root = n1;
n1.left = n2;
n1.right = n3;
n2.left = n4;
n2.right = n5;
n3.left = n6;
}
}
2.5.2二叉树的遍历
1.前中后序遍历
遍历指沿着某条搜索路线依次对树中每个节点均作一次且仅作一次访问。访问节点所做的操作依靠于具体的应用问题比如打印节点的内容节点内容+1。遍历二叉树是最重要的操作之一又是最基础的操作。
在遍历二叉树时如果没有进行某种约定每个人都可以按照自己的想法来实现那么所得到的结果比较混乱。如果我们按照某种规则进行约定则每个人对于同一棵树的遍历结构是相同的。如果N代表根节点L代表根节点的左子树R代表根节点的右子树则根据遍历根节点的先后次序有以下遍历方式
NLR前序遍历先访问根节点再访问根的左子树最后访问根的右子树。
LNR中序遍历先访问根的左子树再访问根节点最后访问根的右子树。
LRN后续遍历先访问根的左子树再访问根的右子树最后访问根节点。
我们根据自己的理解画图
前序遍历的结果1 2 3 4 5 6
中序遍历的结果3 2 1 5 4 6
后续遍历的结果3 2 5 6 4 1
接下来我们完成前中后序遍历的代码
//简单创建一个二叉树
class BinaryTree {
public static class Node{
Node left;
Node right;
int val;
public Node(int val) {
this.val = val;
}
}
private Node root;
//并不是真正创建二叉树的方式但这里我们只是方便理解
public void createBinaryTree() {
Node n1 = new Node(1);
Node n2 = new Node(2);
Node n3 = new Node(3);
Node n4 = new Node(4);
Node n5 = new Node(5);
Node n6 = new Node(6);
root = n1;
n1.left = n2;
n1.right = n3;
n2.left = n4;
n2.right = n5;
n3.left = n6;
}
//前序遍历
public void preOrder(Node root) {
if(root == null) {
return;
}
System.out.print(root.val + " ");
preOrder(root.left);
preOrder(root.right);
}
//中序遍历
public void inOrder(Node root) {
if(root == null) {
return;
}
inOrder(root.left);
System.out.print(root.val + " ");
inOrder(root.right);
}
//后续遍历
public void postOrder(Node root) {
if(root == null) {
return;
}
postOrder(root.left);
postOrder(root.right);
System.out.print(root.val + " ");
}
public static void main(String[] args) {
BinaryTree tree = new BinaryTree();
tree.createBinaryTree();
tree.preOrder(tree.root);
System.out.println();
tree.inOrder(tree.root);
System.out.println();
tree.postOrder(tree.root);
}
}
2.层序遍历
层序遍历除了先序遍历、中序遍历、后续遍历外还可以对二叉树进行层序遍历。设二叉树的根节点所在的层数为1层序遍历就是从所在二叉树的根节点出发首先访问第一层的根节点让后从左往右访问第二层上的根节点依次类推自上而下从左往右逐层的访问树的节点的过程就是层序遍历。
【选择题】
某个完全二叉树按层次输出同一层从左到右的序列为ABCDEFGH。则该完全二叉树的前序遍历顺序为ABDHECFG
二叉树的前序遍历和中序遍历如下先序遍历EFHIGJK中序遍历HFIEJKG则二叉树的后续遍历是HIFKJGE
设一颗二叉树的中序遍历badce,后序遍历bdeca则二叉树前序为abcde
某二叉树的后序遍历和中序遍历均为ABCDEF按照层次输出从一层从左到右的序列为FEDCBA
2.5.3模拟实现二叉树的基本操作
//模拟实现二叉树的基本操作
class Node{
int val;
Node left;
Node right;
public Node(int val) {
this.val = val;
}
}
class Tree {
Node root;
public Tree(){
}
public Tree(Node root) {
this.root = root;
}
// 获取树中节点的个数
int size(Node root){
if(root == null) {
return 0;
}
int leftCount = size(root.left);
int rightCount = size(root.right);
return leftCount + rightCount + 1;
}
// 获取叶子节点的个数
int getLeafNodeCount(Node root) {
if(root == null) {
return 0;
}
if(root.left == null && root.right == null) {
return 1;
}
int leftCount = getLeafNodeCount(root.left);
int rightCount = getLeafNodeCount(root.right);
return leftCount + rightCount;
}
// 获取第K层节点的个数
int getKLevelNodeCount(Node root,int k) {
if(k == 0 || root == null) {
return 0;
}
if(k == 1) {
return 1;
}
int count = 0;
return getKLevelNodeCount(root.left, k - 1) + getKLevelNodeCount(root.right, k - 1);
}
// 获取二叉树的高度
int getHeight(Node root) {
if(root == null) {
return 0;
}
int leftCount = getHeight(root.left);
int rightCount = getHeight(root.right);
return ((leftCount > rightCount) ? leftCount:rightCount) + 1;
}
// 检测值为value的元素是否存在
Node find(Node root, int val) {
if(root == null) {
return null;
}
if(root.val == val) {
return root;
}
Node ret1 = find(root.left, val);
Node ret2 = find(root.right, val);
if(ret1 != null) {
return ret1;
}
return ret2;
}
//这两个较难我们最后再看
//层序遍历
void levelOrder(Node root) {
if(root == null) {
return;
}
Queue<Node> q = new LinkedList<>();
Node cur = root;
q.offer(cur);
while (!q.isEmpty()) {
cur = q.poll();
System.out.print(cur.val + " ");
if(cur.left != null) {
q.offer(cur.left);
}
if(cur.right != null) {
q.offer(cur.right);
}
}
System.out.println();
}
// 判断一棵树是不是完全二叉树
boolean isCompleteTree(Node root) {
if(root == null) {
return true;
}
Node cur = root;
Queue<Node> q = new LinkedList<>();
q.offer(cur);
while(true) {
cur = q.poll();
if(cur != null) {
q.offer(cur.left);
q.offer(cur.right);
}else {
break;
}
}
while(!q.isEmpty()) {
cur = q.poll();
if(cur != null) {
return false;
}
}
return true;
}
}
public class Test {
public static void main(String[] args) {
Node n1 = new Node(1);
Node n2 = new Node(2);
Node n3 = new Node(3);
Node n4 = new Node(4);
Node n5 = new Node(5);
Node n6 = new Node(6);
Tree t = new Tree();
t.root = n1;
n1.left = n2;
n1.right = n3;
n2.left = n4;
n2.right = n5;
n3.left = n6;
System.out.println("=================输出节点个数================");
System.out.println(t.size(t.root));
System.out.println("=================输出叶子节点数===============");
System.out.println(t.getLeafNodeCount(t.root));
System.out.println("================输出第K层节点个数==============");
System.out.println(t.getKLevelNodeCount(t.root, 2));
System.out.println("================二叉树的高度=================");
System.out.println(t.getHeight(t.root));
System.out.println("================检测是否包含某一元素============");
System.out.println(t.find(t.root, 5));//这里不能直接输出值防止为空时报错
System.out.println(t.find(t.root, 9));
System.out.println("=================完全二叉树的判断=============");
System.out.println(t.isCompleteTree(t.root));
System.out.println("=================层序遍历====================");
t.levelOrder(t.root);
}
}
2.6二叉树相关习题
检查两棵树是否相同。
//检查两颗树是否相同
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 boolean isSameTree(TreeNode p, TreeNode q) {
if(q == null && p == null) {
return true;
}else if(q == null || p == null) {
return false;
}
if (q.val != p.val) {
return false;
}
boolean ret1 = isSameTree(p.left, q.left);
boolean ret2 = isSameTree(p.right, q.right);
return ret1 && ret2;
}
}检测一棵树是否是另一棵树的子树自身也是自身的子树
/**
* 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 boolean isSameTree(TreeNode p, TreeNode q) {
if(q == null && p == null) {
return true;
}else if(q == null || p == null) {
return false;
}
if (q.val != p.val) {
return false;
}
boolean ret1 = isSameTree(p.left, q.left);
boolean ret2 = isSameTree(p.right, q.right);
return ret1 && ret2;
}
//检测一棵树是否是另一棵树的子树自身也是自身的子树
public boolean isSubtree(TreeNode root, TreeNode subRoot) {
if (subRoot == null) {
return true;
}
if(root == null) {
return false;
}
boolean ret = isSameTree(root, subRoot);
if(ret) {
return true;
}
boolean ret1 = isSubtree(root.left, subRoot);
boolean ret2 = isSubtree(root.right, subRoot);
return ret1 || ret2;
}
}反转二叉树
/**
* 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 TreeNode invertTree(TreeNode root) {
if(root == null) {
return null;
}
if(root.left == null && root.right == null) {
return root;
}
invertTree(root.left);
invertTree(root.right);
TreeNode tmp;
tmp = root.left;
root.left = root.right;
root.right = tmp;
return root;
}
}判断一颗二叉树是否是平衡树
【平衡树】每颗二叉树的左右子树的高度差不大于1
/**
* 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 boolean isBalanced(TreeNode root) {
if(getHeight(root) == -1) {
return false;
}
return true;
}
private int getHeight(TreeNode root) {
if(root == null) {
return 0;
}
int leftHeight = getHeight(root.left);
int rightHeight = getHeight(root.right);
if(leftHeight == -1 || rightHeight == -1) {
return -1;
}
if(Math.abs(leftHeight - rightHeight) > 1 ) {
return -1;
}else {
return Math.max(leftHeight, rightHeight) + 1;
}
}
}判断一棵树是否是轴对称
/**
* 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 boolean isSymmetric(TreeNode root) {
if(root == null) {
return true;
}
return isSymmetric2(root.left, root.right);
}
private boolean isSymmetric2(TreeNode root1, TreeNode root2) {
if(root1 == null && root2 == null) {
return true;
}
if(root1 == null || root2 == null) {
return false;
}
if(root1.val != root2.val) {
return false;
}
boolean ret1 = isSymmetric2(root1.left, root2.right);
if(ret1 == false) {
return false;
}
boolean ret2 = isSymmetric2(root1.right, root2.left);
return ret2;
}
}输入一个二叉树的前序遍历要求构建这个二叉树然后输出中序遍历的结果。输入的前序遍历如果某个节点为null,前序遍历中则用#代替
import java.util.Scanner;
/**
* Describe:输入一个二叉树的前序遍历要求构建这个二叉树
* 然后输出中序遍历的结果。输入的前序遍历如果某个节点为null,前序遍历中则用#代替
* User:lenovo
* Date:2023-01-18
* Time:17:08
*/
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
class Node {
char val;
Node left = null;
Node right = null;
public Node(char val) {
this.val = val;
}
public Node() {
}
}
class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNext()) {
String s = in.nextLine();
Node root = new Node();
root = buildTree(root, s);
show(root);
System.out.println();
}
}
public static int i = 0;
public static Node buildTree(Node root, String s) {
char tmp = s.charAt(i);
if(tmp == '#') {
return null;
}
root = new Node(tmp);
i = i + 1;
root.left = buildTree(root.left, s);
i++;
root.right = buildTree(root.right, s);
return root;
}
public static void show(Node root) {
if(root == null) {
return;
}
show(root.left);
System.out.print(root.val + " ");
show(root.right);
}
}
二叉树的分层遍历二叉树常用的方法中有答案
我们创立一个queue用于存放二叉树的各个节点
我们先将root放入队列
我们弹出队列中的元素并打印判断此节点的左节点是否为空不为空放入队列右节点是否为空不为空放入队列直到队列完全为空
换行
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先 。
【公共祖先】从根节点到此节点两个路径相遇的节点。
【解析】我们把它根据是否包含pq中的任意一个可分为三种情况
左子树包含右子树不包含
左子树不包含右子树包含
左右子树都包含放回根节点
根据这三种情况返回不同的节点即可。
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null || root == p || root == q) return root;
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
if(left == null) return right;
if(right == null) return left;
return root;
}
}根据一颗树的前序遍历和中序遍历构建二叉树。
【解析】
我们先看前序遍历第一个就是根节点把它放入二叉树中然后在中序遍历中找根节点的坐标
在中序遍历的根节点的左边是这个树的左子树右边是右子树
根节点的左子树根据前序遍历的性质先根后左再右按照原来的方法再次执行
根节点的右子树按照原来的方法再次执行
返回根节点
【难点】前序遍历需要一个全局变量来控制以便真正能够遍历一遍每次找到根节点时我们要知道在中序遍历中这个根节点对应的左子树的范围和右子树的范围。
/**
* 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 {
private int pi = 0;
public TreeNode buildTree(int[] preorder, int[] inorder) {
pi = 0;
return build(preorder, inorder, 0, inorder.length - 1);
}
public TreeNode build(int[] preorder, int[] inorder, int ib, int ie) {
if(ib > ie) {
return null;
}
int key = preorder[pi];
pi++;
TreeNode root = new TreeNode(key);
int i = 0;
for(i = ib; i < ie; i++) {
if(inorder[i] == key) {
break;
}
}
root.left = build(preorder, inorder, ib, i-1);
root.right = build(preorder, inorder, i+1, ie);
return root;
}
}根据一颗树的中序遍历和后续遍历构造二叉树与上题基本相同
/**
* 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 {
private int pi = 0;
public TreeNode buildTree(int[] inorder, int[] postorder) {
pi = postorder.length - 1;
return build(inorder, postorder, 0, pi);
}
public TreeNode build(int[] inorder, int[] postorder, int left, int right) {
if(left > right) {
return null;
}
int key = postorder[pi];
pi--;
TreeNode root = new TreeNode(key);
int i = 0;
for(i = left; i < right + 1; i++) {
if(inorder[i] == key) {
break;
}
}
root.right = build(inorder, postorder, i + 1, right);
root.left = build(inorder, postorder, left, i - 1);
return root;
}
}根据二叉树按照前序遍历的方式创建字符串要求左子树要跟在根节点的后面用括号括住左子树右子树要跟在左子树的后面用括号括住右子树。
/**
* 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 String tree2str(TreeNode root) {
return func(root).toString();
}
private StringBuilder func(TreeNode root) {
if(root == null) {
return null;
}
StringBuilder s = new StringBuilder();
s.append(root.val);
if(root.left == null && root.right == null) {
return s;
}else {
if(root.left != null) {
s.append('(');
s.append(func(root.left));
s.append(')');
}else {
s.append('(');
//s.append(func(root.left));
s.append(')');
}
}
if(root.right == null) {
return s;
}else {
s.append('(');
s.append(func(root.right));
s.append(')');
}
return s;
}
}二叉树的前序遍历非递归
【解析】此题还是比较难的。
我们先创建一个ArrayList对象名为list用于存放前序遍历的顺序
再创建一个Stack对象用于存放没有走到右子树的节点以便我们遇到cur = null时我们能找到上父节点的右子树。我们采用Stack的目的是我们需要的是后进先出的情况
接下来我们让cur = cur.left让它一直往左走如果不为空放入stack和list如果遇到了空我们弹出刚刚进入栈的元素走这个元素的右子树。此时cur=null,我们没有将它放入stack所以弹出的是cur的父节点
本题最难的和最难想出来的是总的循环条件我们要保证cur = null和stack为空时才能退出循环
最后返回list
/**
* 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 List<Integer> preorderTraversal(TreeNode root) {
if(root == null) {
return new ArrayList<>();
//return null;
}
List<Integer> list = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
while(cur != null || !stack.isEmpty()) {
while(cur != null) {
stack.push(cur);
list.add(cur.val);
cur = cur.left;
}
TreeNode key = stack.pop();
cur = key.right;
}
return list;
}
}二叉树的中序遍历非递归
请先了解非递归的前序遍历的方法上题
此题与上题不同的是进入list的时机不同我们遇到cur = null时我们才会讲这个节点的父节点放入list同时又会让cur = 父节点.right
循环往下进行直到不符合条件
返回null.
/**
* 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 List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
if(root == null) {
return list;
}
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
while(cur != null || !stack.isEmpty()) {
if(cur != null) {
stack.push(cur);
cur = cur.left;
}else {
TreeNode key = stack.pop();
list.add(key.val);
cur = key.right;
}
}
return list;
}
}二叉树的后序遍历非递归
此题和前两题不同
这里我们新增了一个Stack名为past用于记录哪些节点已经走过右边。为了方便判断是否该往右边走或进入list
我们还是先让cur != null的元素进入stack;
如果cur = null我们要判断key(stack弹出的元素即没有走右边的元素)是否走过右边没走过往右边走走右边了key放入liststack和past要弹出元素
重复此循环直到条件不满足
/**
* 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 List<Integer> postorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
if(root == null) {
return list;
}
TreeNode cur = root;
Stack<TreeNode> stack = new Stack<>();
TreeNode prev = new TreeNode();
//Stack<TreeNode> past = new Stack<>();
while(cur != null || !stack.isEmpty()) {
if(cur != null) {
stack.push(cur);
cur = cur.left;
}else {
/*TreeNode key = stack.peek();
if(!past.isEmpty() && key == past.peek()) {
list.add(key.val);
stack.pop();
past.pop();
//cur = stack.peek().right;
}else {
cur = key.right;
past.push(key);
}
*/
TreeNode key = stack.peek();
if(key.right == null || key.right == prev) {
list.add(key.val);
stack.pop();
prev = key;
}else {
cur = key.right;
}
}
}
return list;
}
}希望大家多多支持与鼓励如有相关问题请留言