二叉树的基本操作
二叉树的遍历(前中后层)
所谓遍历(Traversal)是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作 依赖于具体的应用问题(比如：打印节点内容、节点内容加1)。 遍历是二叉树上最重要的操作之一，是二叉树上进行其它运算之基础。
在遍历二叉树时，如果没有进行某种约定，每个人都按照自己的方式遍历，得出的结果就比较混乱，如果按照某种规则进行约定，则每个人对于同一棵树的遍历结果肯定是相同的。如果N代表根节点，L代表根节点的左子树，R代 表根节点的右子树，则根据遍历根节点的先后次序有以下四种遍历方式：
1.NLR：前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点—>根的左子树—>根的右子树。
2.LNR：中序遍历(Inorder Traversal)——根的左子树—>根节点—>根的右子树。
3.LRN：后序遍历(Postorder Traversal)——根的左子树—>根的右子树—>根节点。
4.层序遍历：设二叉树的根节点所在层数为1，层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从 左到右访问第2层上的节点，接着是第三层的节点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是 层序遍历。
由于被访问的结点必是某子树的根，所以N(Node）、L(Left subtree）和R(Right subtree）又可解释为根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。
注意事项
1:事实上只要牵扯到二叉树相关的面试题的时候基本上他的解决方式就是依赖于这4种遍历。
2:二叉树的习题，如果不要求使用非递归，基本上全是递归，而且是多路递归.
小练习
给出下列二叉树的三种遍历结果:
前序遍历：ABDEHCFG
中序遍历：DBEHAFCG
后序遍历： DHEBFGCA
二叉树的基本操作(递归代码实现)
对于二叉树的操作也是非常的多：下面我们给出几个操作自己来实现下，加深对于二叉树的理解:
// 前序遍历 void preOrderTraversal(Node root); // 中序遍历 void inOrderTraversal(Node root); // 后序遍历 void postOrderTraversal(Node root); // 遍历思路-求结点个数 static int size = 0; void getSize1(Node root); // 子问题思路-求结点个数 int getSize2(Node root); // 遍历思路-求叶子结点个数 static int leafSize = 0; void getLeafSize1(Node root); // 子问题思路-求叶子结点个数 int getLeafSize2(Node root); // 子问题思路-求第 k 层结点个数 int getKLevelSize(Node root); // 获取二叉树的高度 int getHeight(Node root); // 查找 val 所在结点，没有找到返回 null // 按照 根 -> 左子树 -> 右子树的顺序进行查找 // 一旦找到，立即返回，不需要继续在其他位置查找 Node find(Node root, int val);
在对于二叉树的基本操作的代码中,我们此处二叉树的存储方式默认是链式存储法，存储方式为二叉方式，也就是孩子表示法。
我们所选的二叉树如下所示，后续所有的操作也是针对于这个二叉树进行的:
下面来看代码实现:
class BTNode { public char val; //左子树的引用 public BTNode left; //右子树的引用 public BTNode right; public BTNode(char val) { this.val = val; } @Override public String toString() { return "val" + this.val; } } public class Bitree { /** * 我们要首先创建二叉树，但是为了好理解，我们先以穷举的方式创建二叉树 * 后期我们会以遍历的方式创建二叉树 * 当前使用穷举的方式只是权宜之计 * * @return */ public BTNode createTree() { BTNode A = new BTNode('A'); BTNode B = new BTNode('B'); BTNode C = new BTNode('C'); BTNode D = new BTNode('D'); BTNode E = new BTNode('E'); BTNode F = new BTNode('F'); BTNode G = new BTNode('G'); BTNode H = new BTNode('H'); A.left = B; A.right = C; B.left = D; B.right = E; E.right = H; C.left = F; C.right = G; return A; } // 前序遍历,root为根节点 //此时需要使用递归，递归的思想就是大问题化简成小问题 void preOrderTraversal(BTNode root) { if (root == null) { return; } System.out.print(root.val); preOrderTraversal(root.left); preOrderTraversal(root.right); } // 中序遍历,root为根节点 void inOrderTraversal(BTNode root) { if (root == null) { return; } inOrderTraversal(root.left); System.out.print(root.val); inOrderTraversal(root.right); } // 后序遍历,root为根节点 void postOrderTraversal(BTNode root) { if (root == null) { return; } postOrderTraversal(root.left); postOrderTraversal(root.right); System.out.print(root.val); } /** * 求树的节点个数有两种方式 * 1：遍历思路求节点个数：递归遍历，每次只要不为空，size++ * 2：子问题思路求节点个数:要求整棵树的节点个数：等于左树节点数+右树节点数+1 */ // 遍历思路-求结点个数 static int size = 0; void getSize1(BTNode root) { if (root == null) { return; } size++; getSize1(root.left); getSize1(root.right); } // 子问题思路-求结点个数 int getSize2(BTNode root) { if (root == null) { return 0; } return getSize2(root.left) + getSize2(root.right) + 1; } // 遍历思路-求叶子结点个数 static int leafSize = 0; void getLeafSize1(BTNode root) { if (root == null) { return; } if (root.left == null && root.right == null) { leafSize++; } getLeafSize1(root.left); getLeafSize1(root.right); } // 子问题思路-求叶子结点个数 //叶子节点个数等于根节点左子树中叶子节点个数加右子树中叶子节点个数 int getLeafSize2(BTNode root) { if (root == null) { return 0; } if (root.left == null && root.right == null) { return 1; } return getLeafSize2(root.left) + getLeafSize2(root.right); } // 子问题思路-求第 k 层结点个数 /*这个方法应该这样求解:首先求第k层的节点个数，实际上就是求根节点左子树第k-1层的节点个数加根节点右子树第k-1层节点的个数 假如一个二叉树此时有四层，我们要求第三层节点的个数，实际上就是求根节点左子树第二层节点的个数加上根节点右子树第二层节点的个数 */ int getKLevelSize(BTNode root, int k) { if (root == null) { return 0; } if (k == 1) { return 1; } return getKLevelSize(root.left, k - 1) + getKLevelSize(root.right, k - 1); } // 获取二叉树的高度 /* 二叉树的高度在获取的时候一般使用子问题的思路 即二叉树的高度=左子树的高度和右子树的高度中较大的一者+1后的值 */ int getHeight(BTNode root) { if (root == null) { return 0; } return getHeight(root.left) > getHeight(root.right) ? getHeight(root.left) + 1 : getHeight(root.right) + 1; } // 查找 val 所在结点，没有找到返回 null // 按照 根 -> 左子树 -> 右子树的顺序进行查找 // 一旦找到，立即返回，不需要继续在其他位置查找 BTNode find(BTNode root, char val) { if (root == null) { return null; } if (root.val == val) { return root; } BTNode btNode = find(root.left, val); BTNode btNode1 = find(root.right, val); return btNode == null ? btNode1 : btNode; } }
程序对应测试类:
public class TestDemo { public static void main(String[] args) { Bitree binaryTree = new Bitree(); //创建一个二叉树，并获得它的根节点 BTNode root = binaryTree.createTree(); //进行先序遍历,并进行输出，结果为ABDEHCFG binaryTree.preOrderTraversal(root); System.out.println(); //获取结点个数 binaryTree.getSize1(root); //8 System.out.println(Bitree.size); int count1 = binaryTree.getSize2(root); //8 System.out.println(count1); //获取叶子结点个数 binaryTree.getLeafSize1(root); //4 System.out.println(Bitree.leafSize); int count = binaryTree.getLeafSize2(root); //4 System.out.println(count); //获取第k层节点的个数 //结果为4 System.out.println(binaryTree.getKLevelSize(root, 3)); //求二叉树的高度,结果为4 System.out.println(binaryTree.getHeight(root)); //查找 val 所在结点，没有找到返回 null BTNode bitree = binaryTree.find(root, 'H'); if (bitree == null) { System.out.println("二叉树中没有这个节点"); return; } char ch = bitree.val; //输出结果为:找到了这个节点，其val为 + H System.out.println("找到了这个节点，其val为" + ch); } }
关于二叉树的基础面试题(重要,必须全部掌握)
1.二叉树的前序遍历。 OJ链接
2.二叉树中序遍历 。OJ链接
3.二叉树的后序遍历 。OJ链接
4.检查两颗树是否相同。OJ链接
5.另一颗树的子树。OJ链接
6.二叉树最大深度。OJ链接
7.判断一颗二叉树是否是平衡二叉树。OJ链接
8.对称二叉树。OJ链接
9.递增顺序查找树. OJ链接
10.合并二叉树.OJ链接
二叉树的层序遍历
设二叉树的根节点所在层数为1，层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第2层上的节点，接着是第三层的节点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是 层序遍历。
层序遍历的基本操作(代码实现)
我们使用队列来实现我们的的层序遍历操作,首先我们给出要实现的方法：
// 层序遍历 void levelOrderTraversal(Node root); // 判断一棵树是不是完全二叉树 boolean isCompleteTree(Node root);
使用队列来实现我们二叉树的层序遍历的思路如下：
此处我们还是以这棵树为例子:
1:首先判断二叉树的根节点是否为空，如果不为空，就将二叉树的根节点先从队尾入队列
2:然后判断这个队列是否为空，如果不为空，就将队头元素出栈，将出队的元素保存到一个临时变量cur处，并打印这个出队的元素.此时我们将A出栈，并保留到cur这个变量中，注意此时cur的值为A
3:然后我们再判断当前cur的左子树和右子树是否为空，如果不为空 就依次将cur的左子树和右子树分别入队：如下所示:
然后将队头元素B出队，替换之前 cur中的 变量A ，并打印B,然后判断当前B的左子树的元素是否为空，我们发现是D,不为空，就将D入队列，然后判断B的右子树的元素是否为空，我们发现是E,不为空，继续入队列，如下所示：
4：然后再判断队列是否为空，如果不为空，就将队头元素C进行出队操作,然后将我们的cur变量替换成C,并打印我们的C
5:此时继续判断C的左子树的元素是否为空，我们发现是F,不为空，就将F这个元素入队列，然后继续判断C的右子树的元素是否为空，我们发现是G,不为空，继续将G这个元素入队列，如下所示:
6:此时队列非空，则将队列的头元素D出队，此时cur变量存储的元素为D,然后打印我们的D，然后判断D的左子树和右子树是否非空，发现为空，则不入队.
7:此时队列非空,继续将E这个元素出队，此时cur变量存储的元素为E,打印E，然后判断E的左子树和右子树是否非空，发现左子树为空，右子树不为空，为H，则将右子树的元素H进行入队操作
8:此时队列非空，则将队头元素F进行出队操作,cur变量此时存储的是我们的F，然后打印F,此时再判断F的左子树和右子树是否非空，发现为空，则不入队.
9:此时队列非空，则将队头元素G进行出队操作,cur变量此时存储的是我们的G，然后保存打印G,此时再判断G的左子树和右子树是否非空，发现为空，则不入队.
10:此时队列非空，则将队头元素H进行出队操作,cur变量此时存储的是我们的H，然后保存打印H,此时再判断H的左子树和右子树是否非空，发现为空，则不入队
11:最终我们的队列为空，为空后我们的层序遍历就结束了
下面来看我们的代码实现:
首先是我们自己实现的levelOrderTraversal方法
class BTNode { public char val; //左子树的引用 public BTNode left; //右子树的引用 public BTNode right; public BTNode(char val) { this.val = val; } } public class Bitree { /** * 我们要首先创建二叉树，但是为了好理解，我们先以穷举的方式创建二叉树 * 后期我们会以遍历的方式创建二叉树 * 当前使用穷举的方式只是权宜之计 * * @return */ public BTNode createTree() { BTNode A = new BTNode('A'); BTNode B = new BTNode('B'); BTNode C = new BTNode('C'); BTNode D = new BTNode('D'); BTNode E = new BTNode('E'); BTNode F = new BTNode('F'); BTNode G = new BTNode('G'); BTNode H = new BTNode('H'); A.left = B; A.right = C; B.left = D; B.right = E; E.right = H; C.left = F; C.right = G; return A; } //层序遍历 void levelOrderTraversal(BTNode root) { Queue<BTNode> queue = new LinkedList<>(); if (root == null) { return; } queue.add(root); while (!queue.isEmpty()) { BTNode cur = queue.poll(); System.out.print(cur.val + ""); if (cur.left != null) { queue.add(cur.left); } if (cur.right != null) { queue.add(cur.right); } } } }
来看测试类:
public class TestDemo { public static void main(String[] args) { Bitree binaryTree = new Bitree(); //创建一个二叉树，并获得它的根节点 BTNode root = binaryTree.createTree(); //层序遍历 //输出结果为ABCDEFGH binaryTree.levelOrderTraversal(root); } }
接着往下走，我们继续来看完全二叉树的判断，判断一棵树是否为完全二叉树的思路我们还是沿用层序遍历的思路，只不过我们是判断每次从队列出来的队头元素和剩余队列中的元素是否为空，当满足从队列出来的队头元素为空和剩余队列中的元素不为空的情况，就说明其不是一个完全二叉树，下面我们来书写所给的isCompleteTree方法，并给出代码和测试类:
此处我们对一个树是否为二叉树使用的例子还是下面这颗二叉树:
很明显这不是一颗完全二叉树，所以最终的判断的结果应该为false.
代码实现:
class BTNode { public char val; //左子树的引用 public BTNode left; //右子树的引用 public BTNode right; public BTNode(char val) { this.val = val; } } public class Bitree { /** * 我们要首先创建二叉树，但是为了好理解，我们先以穷举的方式创建二叉树 * 后期我们会以遍历的方式创建二叉树 * 当前使用穷举的方式只是权宜之计 * * @return */ public BTNode createTree() { BTNode A = new BTNode('A'); BTNode B = new BTNode('B'); BTNode C = new BTNode('C'); BTNode D = new BTNode('D'); BTNode E = new BTNode('E'); BTNode F = new BTNode('F'); BTNode G = new BTNode('G'); BTNode H = new BTNode('H'); A.left = B; A.right = C; B.left = D; B.right = E; E.right = H; C.left = F; C.right = G; return A; } //完全二叉树的判断 boolean isCompleteTree(BTNode root) { if(root == null) { return true; } Queue<BTNode> queue = new LinkedList<>(); queue.offer(root); while(!queue.isEmpty()) { BTNode cur = queue.poll(); if(cur != null) { queue.offer(cur.left); queue.offer(cur.right); }else { //发现为空直接跳出循环 break; } } //此时判断队列剩下的是否还有元素，如果有，说明不是完全二叉树 while(!queue.isEmpty()) { BTNode node = queue.peek(); if(node != null) { return false; }else { queue.poll(); } } return true; } }
测试类:
public class TestDemo { public static void main(String[] args) { Bitree binaryTree = new Bitree(); //创建一个二叉树，并获得它的根节点 BTNode root = binaryTree.createTree(); //完全二叉树的判断 //输出结果为false System.out.println(binaryTree.isCompleteTree(root)); } }
进阶面试题(重要)
二叉树的构建及遍历OJ链接(必须掌握)
二叉树的层序遍历 OJ链接(必须掌握)
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先 OJ链接（面试常考)
二叉树搜索树转换成排序双向链表OJ链接（考过一次)
根据一棵树的前序遍历与中序遍历构造二叉树OJ链接
根据一棵树的中序遍历与后序遍历构造二叉树OJ链接
二叉树最大宽度 OJ链接
二叉树创建字符串 OJ链接(比较难，可以不掌握)
完全二叉树的判断OJ链接
二叉树前中后序的非递归实现
二叉树递归改非递归实现一般使用的就是队列或者栈，在这里我们就用栈来实现我们二叉树前中后序的非递归遍历
此处我们所使用的二叉树如下所示:
// 前序遍历 void preOrderTraversal(Node root); // 中序遍历 void inOrderTraversal(Node root); // 后序遍历 void postOrderTraversal(Node root);
前序遍历非递归实现
思路
首先我们来讲解前序遍历的非递归实现的思路
1:首先定义一个变量cur，一开始我们的cur是指向我们的根节点root,然后定义一个空栈,如下图所示:
2:此时cur所指向的节点不为空，就打印我们的非空节点,所以此时打印的是我们的A节点，同时将A这个节点进行入栈操作.
3：然后cur依次遍历它的左子树，如果不为空就全部都入栈，同时打印我们的B，D两个节点，所以此时入栈的节点有B，D两个节点
4：然后cur继续遍历左子树，此时D的左子树发现为空，那么cur应该往D节点的右子树走了，所以此时需要额外定义一个top，用于存储我们当前的栈顶元素:所以当cur走到D的左子树为空的时候，就将当前的栈顶元素D弹出，存储到我们的top中，此时让cur=top.right,那么现在cur就指向了D的右子树，但是此时D的右子树为空，所以继续弹出当前的栈顶元素B，把B存到top中，让cur=top.right,所以此时cur指向了我们的B的右子树E,发现E不为空，把E打印完成后入栈，然后cur此时走到E的左子树，发现为空，则将当前栈顶元素E出栈，存入top中，让cur = top.right,此时cur指向我们E的右子树H,发现H不为空，则打印我们的H，然后将H入栈.
5:此时cur继续走，走到H的左子树，发现为空，则将当前栈顶元素H进行出栈，存入到top中，并让cur = top.right，那么cur就走到了H的右子树，发现H的右子树为空，则让当前栈顶元素A出栈，存入到top中，并让cur = top.right,那么cur就走到了A的右子树C,发现C不为空，打印C，并将C入栈
6:cur此时继续往下走，走到了C的左子树F，发现非空，则继续打印F,然后将F入栈，cur继续走到了F的左子树，发现为空，则将当前的栈顶元素F出栈，将其赋给top,然后让cur = top.right，则cur此时走到了F的右子树，发现为空，则将当前栈顶元素C出栈，将其赋给top,然后让cur = top.right，则cur此时走到了C的右子树，发现为G，且G不为空，则打印G，并将其入栈，然后cur继续走到了G的左子树，发现 为空，则将当前的栈顶元素G进行出栈，将其赋给top,然后让cur = top.right，则cur此时走到了G的右子树，发现为空，当想弹出栈顶元素时发现栈已经为空了，则说明我们前序遍历已经完成了
代码实现
上述就是我们在实现二叉树前序遍历非递归的一个整体思路，当然代码照这个思路写还有点问题，不过核心思路就如上述所看到的一样，下面我们先来进行代码实现:
这次的代码实现我们采用一个循序渐进的方式来展现：
1：首先是按照我们之前的思路把整体的代码架子搭起来，来看代码：
void preOrderTraversalNor(BTNode root) { if (root == null) { return; } Stack<BTNode> stack = new Stack<>(); BTNode cur = root; while (cur != null) { stack.push(cur); System.out.print(cur.val + " "); cur = cur.left; } BTNode top = stack.pop(); cur = top.right; }
2:按照上述的代码我们发现并不适用于这种情况:
当D出栈赋给我们的top后，此时cur = top.right后，cur就指向了我们的K，K非空，按理来说是要入栈的，但是程序走到cur = top.right后程序就走完了，K根本入不了栈，说明此时我们的当前这个while循环外面应该还有一个while循环，而这个思路才是非递归中最难想到的一点
此时我们先加上这个while循环：来看代码：
void preOrderTraversalNor(BTNode root) { if (root == null) { return; } Stack<BTNode> stack = new Stack<>(); BTNode cur = root; while (cur != null) { while (cur != null) { stack.push(cur); System.out.print(cur.val + " "); cur = cur.left; } BTNode top = stack.pop(); cur = top.right; } }
现在这个代码看起来貌似没啥问题，但是假如刚才K那个位置确实是null，即D的右子树为null,那么就算加了外层这个循环，cur也到不了B的右子树E处，原因是当cur走到了D的右子树为空的时候，外层while循环进不来，执行不了下面这两段代码:
BTNode top = stack.pop(); cur = top.right;
没有这两段代码，cur就到不了B的右子树E处，所以我们需要加上另外一个条件，即就算cur此时为null,但是栈不为空也可以进入循环
最终的代码实现如下：
class BTNode { public char val; //左子树的引用 public BTNode left; //右子树的引用 public BTNode right; public BTNode(char val) { this.val = val; } } public class Bitree { /** * 我们要首先创建二叉树，但是为了好理解，我们先以穷举的方式创建二叉树 * 后期我们会以遍历的方式创建二叉树 * 当前使用穷举的方式只是权宜之计 * * @return */ public BTNode createTree() { BTNode A = new BTNode('A'); BTNode B = new BTNode('B'); BTNode C = new BTNode('C'); BTNode D = new BTNode('D'); BTNode E = new BTNode('E'); BTNode F = new BTNode('F'); BTNode G = new BTNode('G'); BTNode H = new BTNode('H'); A.left = B; A.right = C; B.left = D; B.right = E; E.right = H; C.left = F; C.right = G; return A; } //前序遍历的非递归解法 void preOrderTraversalNor(BTNode root) { if (root == null) { return; } Stack<BTNode> stack = new Stack<>(); BTNode cur = root; //非递归算法的难点就在于外层的循环 while (cur != null || !stack.isEmpty()) { while (cur != null) { stack.push(cur); System.out.print(cur.val + " "); cur = cur.left; } BTNode top = stack.pop(); cur = top.right; } } }
测试类如下：
public class TestDemo { public static void main(String[] args) { Bitree binaryTree = new Bitree(); //创建一个二叉树，并获得它的根节点 BTNode root = binaryTree.createTree(); //结果为A B D E H C F G binaryTree.preOrderTraversalNor(root); } }
测试结果与前序遍历的递归写法的结果相同，说明方法正确.
中序遍历非递归实现
思路
中序遍历的思路延续我们前序遍历的思路，不同的点是每次当遍历到空元素的时候，前序遍历是将栈顶元素弹出赋给top,并且让cur = top.right,而我们中序遍历是只要遇到空元素，就将栈顶元素弹出赋给top,并且每次都打印弹出的栈顶元素的值，然后再让cur = top.right.
代码示例
inOrderTraversalNor方法实现:
void inOrderTraversalNor(BTNode root) { if (root == null) { return; } Stack<BTNode> stack = new Stack<>(); BTNode cur = root; while (cur != null || !stack.isEmpty()) { while (cur != null) { stack.push(cur); cur = cur.left; } BTNode top = stack.pop(); //变换打印的次序，注意是top.val System.out.print(top.val + " "); cur = top.right; } }
测试类:
public class TestDemo { public static void main(String[] args) { Bitree binaryTree = new Bitree(); //创建一个二叉树，并获得它的根节点 BTNode root = binaryTree.createTree(); //结果为D B E H A F C G binaryTree.inOrderTraversalNor(root); } }
后序遍历非递归实现
思路
后序遍历的思路是这样的：
节点首先还是依次遍历每个节点的左子树，以我们所给的例子为例，当我们遍历到D的左子树的时候为空，原来我们都是当遍历到的节点为空的时候就将栈顶元素出栈，现在我们不能这么做了，以我们所给的二叉树为例子，当我们的cur走到了D的左子树为空的时候，对于后序遍历来说，我们并不知道D的右子树此时是否为空，那么假如我们直接让栈顶元素D出栈然后打印D，此时对于D的右子树来说就直接忽略掉了，所以我们只能使用peek方法来获取栈顶元素，这也是这个算法需要注意的第一个点，然后判断当前栈顶元素D的右子树是否为空，如果为空，出栈顶元素并且打印，不为空的话就让cur指向当前指向当前栈顶元素的右子树
根据上述思路我们可以写出第一版代码:
void postOrderTraversalNor(BTNode root) { if (root == null) { return; } Stack<BTNode> stack = new Stack<>(); BTNode cur = root; while (cur != null || !stack.isEmpty()) { while (cur != null) { stack.push(cur); cur = cur.left; } //注意使用peek而不是poll BTNode top = stack.peek(); if (top.right == null ) { stack.pop(); System.out.print(top.val+" "); } else { cur = top.right; } } }
但是此处需要注意一个点，假设此时D有右子树：如下所示:
此时D的右子树为K，非空，cur指向K，则让K入了栈，然后cur走到了K的左子树为空，既然为空，则使用peek方法获取当前栈顶元素为K,判断K的右子树为null,则将K出栈，并且打印K，然后又经过一个循环，cur因为null，所以直接获取当前栈顶元素D，判断出当前D的右子树非空，则cur此时又指向了D的右子树K，又继续回到循环，判断出cur非空，则又让K入栈了，我们会发现此时陷入了一个死循环
所以我们需要知道哪些节点之前已经打印过了，如果打印过了就不要再被cur指向了，直接出下一个栈顶元素并且打印即可，所以此处我们引用了变量prev，用于记录被打印过的节点，这也是这个算法的第二个核心之处
代码示例
首先来看postOrderTraversalNor方法：
void postOrderTraversalNor(BTNode root) { if (root == null) { return; } Stack<BTNode> stack = new Stack<>(); BTNode cur = root; BTNode prev = null; while (cur != null || !stack.isEmpty()) { while (cur != null) { stack.push(cur); cur = cur.left; } //注意使用peek而不是poll BTNode top = stack.peek(); //每次不但要判断右边是否为空，还要判断右子树的节点是否为上次打印过的节点 if (top.right == null || top.right == prev) { stack.pop(); System.out.print(top.val+" "); //定义一个prev变量，用于每次保存上次打印过的节点 prev = top; } else { cur = top.right; } } }
再来看测试类:
public class TestDemo { public static void main(String[] args) { Bitree binaryTree = new Bitree(); //创建一个二叉树，并获得它的根节点 BTNode root = binaryTree.createTree(); //结果为D H E B F G C A binaryTree.postOrderTraversalNor(root); } }
练习题
1.二叉树前序非递归遍历实现 。OJ链接
2.二叉树中序非递归遍历实现。OJ链接
3.二叉树后序非递归遍历实现。OJ链接
