二叉树的前序,中序,后序遍历方法总结
⼆叉树的前序，中序，后序遍历⽅法总结
⼆叉树的前序遍历，中序遍历，后序遍历是⾯试中常常考察的基本算法，关于它的概念这⾥不再赘述了，还不了解的同学可以去翻翻。
这⾥，我个⼈对这三个遍历顺序理解是：前 中 后 这三个词是针对根节点的访问顺序⽽⾔的，即前序就是根节点在最前根->左->右，中序是根节点在中间左->根->右，后序是根节点在最后左->右->根。
⽆论哪种遍历顺序，⽤递归总是最容易实现的，也是最没有含⾦量的。但我们⾄少要保证能信⼿捏来地把递归写出来，在此基础上，再掌握⾮递归的⽅式。
在⼆叉树的顺序遍历中，常常会发⽣先遇到的节点到后⾯再访问的情况，这和先进后出的栈的结构很相似，因此在⾮递归的实现⽅法中，我们最常使⽤的数据结构就是栈。
今天来总结下⼆叉树前序、中序、后序遍历相互求法，即如果知道两个的遍历，如何求第三种遍历⽅法，⽐较笨的⽅法是画出来⼆叉树，然后根据各种遍历不同的特性来求，也可以编程求出，下⾯我们分别说明。
⾸先，我们看看前序、中序、后序遍历的特性：头像图片显示红旗
前序遍历：
1.访问根节点
2.前序遍历左⼦树
3.前序遍历右⼦树
中序遍历：
1.中序遍历左⼦树
2.访问根节点
3.中序遍历右⼦树
后序遍历：
1.后序遍历左⼦树
2.后序遍历右⼦树
3.访问根节点
音悦台怎么获得积分
⼀、已知前序、中序遍历，求后序遍历
例：
前序遍历:        GDAFEMHZ
中序遍历:        ADEFGHMZ
画树求法：第⼀步，根据前序遍历的特点，我们知道根结点为G
第⼆步，观察中序遍历ADEFGHMZ。其中root节点G左侧的ADEF必然是root的左⼦树，G右侧的HMZ必然是root的右⼦树。
第三步，观察左⼦树ADEF，左⼦树的中的根节点必然是⼤树的root的leftchild。在前序遍历中，⼤树的root的leftchild位于root 之后，所以左⼦树的根节点为D。
第四步，同样的道理，root的右⼦树节点HMZ中的根节点也可以通过前序遍历求得。在前序遍历中，⼀定是先把root和root的所有左⼦树节点遍历完之后才会遍历右⼦树，并且遍历的左⼦树的第⼀个节点就是左⼦树的根节点。同理，遍历的右⼦树的第⼀个节点就是右⼦树的根节点。
第五步，观察发现，上⾯的过程是递归的。先到当前树的根节点，然后划分为左⼦树，右⼦树，然后进⼊左⼦树重复上⾯的过程，然后进⼊右⼦树重复上⾯的过程。最后就可以还原⼀棵树了。该步递归的过程可以简洁表达如下：
1 确定根，确定左⼦树，确定右⼦树。
2 在左⼦树中递归。
3 在右⼦树中递归。
4 打印当前根。
那么，我们可以画出这个⼆叉树的形状：
那么，根据后序的遍历规则，我们可以知道，后序遍历顺序为：AEFDHZMG
⼆、已知中序和后序遍历，求前序遍历
依然是上⾯的题，这次我们只给出中序和后序遍历：
中序遍历:      ADEFGHMZ
后序遍历:      AEFDHZMG
画树求法：第⼀步，根据后序遍历的特点，我们知道后序遍历最后⼀个结点即为根结点，即根结点为G。
第⼆步，观察中序遍历ADEFGHMZ。其中root节点G左侧的ADEF必然是root的左⼦树，G右侧的HMZ必然是root的右⼦树。
第三步，观察左⼦树ADEF，左⼦树的中的根节点必然是⼤树的root的leftchild。在前序遍历中，⼤树的root的leftchild位于root 之后，所以左⼦树的根节点为D。
第四步，同样的道理，root的右⼦树节点HMZ中的根节点也可以通过前序遍历求得。在前后序遍历中，⼀定是先把root和root的所有左⼦树节点遍历完之后才会遍历右⼦树，并且遍历的左⼦树的第⼀个节点就是左⼦树的根节点。同理，遍历的右⼦树的第⼀个节点就是右⼦树的根节点。
第五步，观察发现，上⾯的过程是递归的。先到当前树的根节点，然后划分为左⼦树，右⼦树，然后进⼊左⼦树重复上⾯的过程，然后进⼊右⼦树重复上⾯的过程。最后就可以还原⼀棵树了。该步递归的过程可以简洁表达如下：
1 确定根，确定左⼦树，确定右⼦树。
2 在左⼦树中递归。
3 在右⼦树中递归。
4 打印当前根。
这样，我们就可以画出⼆叉树的形状，如上图所⽰，这⾥就不再赘述。
那么，前序遍历:        GDAFEMHZ
三、已知前序、后序遍历，求中序遍历
（这个结果不唯⼀，你有什么想法呢？）
前序遍历
前序遍历（题⽬见）是三种遍历顺序中最简单的⼀种，因为根节点是最先访问的，⽽我们在访问⼀个树的时候最先遇到的就是根节点。
递归法
递归的⽅法很容易实现，也很容易理解：我们先访问根节点，然后递归访问左⼦树，再递归访问右⼦树，即实现了根->左->右的访问顺序，因为使⽤的是递归⽅法，所以每⼀个⼦树都实现了这样的顺序。
中元节是几月几日return result;
}
private void preorderHelper(TreeNode root, List<Integer> result) {
if (root == null) return;
result.add(root.val); // 访问根节点
preorderHelper(root.left, result); // 递归遍历左⼦树
preorderHelper(root.right, result); //递归遍历右⼦树
}
门事件全图}
迭代法
在迭代法中，我们使⽤栈来实现。由于出栈顺序和⼊栈顺序相反，所以每次添加节点的时候先添加右节点，再添加左节点。这样在下⼀轮访问⼦树的时候，就会先访问左⼦树，再访问右⼦树：
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new LinkedList<>();
if (root == null) return result;
Stack<TreeNode> toVisit = new Stack<>();
toVisit.push(root);
TreeNode cur;达的拼音
while (!toVisit.isEmpty()) {
cur = toVisit.pop();
result.add(cur.val); // 访问根节点
if (cur.right != null) toVisit.push(cur.right); // 右节点⼊栈
if (cur.left != null) toVisit.push(cur.left); // 左节点⼊栈
}
return result;
}
}
中序遍历
中序遍历（题⽬见）相对前序遍历要复杂⼀点，因为我们说过，在⼆叉树的访问中，最先遇到的是根节点，但是在中序遍历中，最先访问的不是根节点，⽽是左节点。（当然，这⾥说复杂是针对⾮递归⽅法⽽⾔的，递归⽅法都是很简单的。）
递归法
⽆论对于哪种⽅式，递归的⽅法总是很容易实现的，也是很符合直觉的。对于中序遍历，就是先访问左⼦树，再访问根节点，再访问右⼦树，即 左->根->右：
return result;
}
private void inorderHelper(TreeNode root, List<Integer> result) {
if(root == null) return;
inorderHelper(root.left, result); // 递归遍历左⼦树
result.add(root.val); // 访问根节点
inorderHelper(root.right, result); // 递归遍历右⼦树
}
}
⼤家可以对⽐它和前序遍历的递归实现，⼆者仅仅是在节点的访问顺序上有差别，代码框架完全⼀致。
迭代法
中序遍历的迭代法要稍微复杂⼀点，因为最先遇到的根节点不是最先访问的，我们需要先访问左⼦树，再回退到根节点，再访问根节点的右⼦树，这⾥的⼀个难点是从左⼦树回退到根节点的操作，虽然可以⽤栈来实现回退，但是要注意在出栈时保存根节点的引⽤，因为我们还需要通过根节点来访问右⼦树：
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new LinkedList<>();
Stack<TreeNode> toVisit = new Stack<>();
TreeNode cur = root;
while (cur != null || !toVisit.isEmpty()) {
while (cur != null) {
toVisit.push(cur); // 添加根节点
cur = cur.left; // 循环添加左节点
}
cur = toVisit.pop(); // 当前栈顶已经是最底层的左节点了，取出栈顶元素，访问该节点
result.add(cur.val);
cur = cur.right; // 添加右节点
}
return result;
}
}
这⾥：
while (cur != null) {
toVisit.push(cur);
cur = cur.left;
}
↑这⼀部分实现了递归添加左节点的作⽤。
cur = toVisit.pop();
result.add(cur.val);
cur = cur.right;
↑这⼀部分实现了对根节点的遍历，同时将指针指向了右⼦树，在下轮中遍历右⼦树。
在看这部分代码中，脑海中要有⼀个概念：当前树的根节点的左节点，是它的左⼦树的根节点。因此从不同的层次上看，左节点也是根节点。另外，LeetCode上也提供了关于中序遍历的动态图的演⽰，感兴趣的读者可以去。
后序遍历
后序遍历（题⽬见）是三种遍历⽅法中最难的，与中序遍历相⽐，虽然都是先访问左⼦树，但是在回退到根节点的时候，后序遍历不会⽴即访问根节点，⽽是先访问根节点的右⼦树，这⾥要⼩⼼的处理⼊栈出栈的顺序。（当然，这⾥说复杂是针对⾮递归⽅法⽽⾔的，递归⽅法都是很简单的。）
每当雪花纷纷飘落是哪首歌的歌词递归法
⽆论对于哪种⽅式，递归的⽅法总是很容易实现的，也是很符合直觉的。对于后序遍历，就是先访问左⼦树，再访问右⼦树，再访问根节点，即 左->右->根：
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> result = new LinkedList<>();
postorderHelper(root, result);
return result;
}
private void postorderHelper(TreeNode root, List<Integer> result) {
if (root == null) return;
postorderHelper(root.left, result); // 遍历左⼦树
postorderHelper(root.right, result); // 遍历右⼦树
result.add(root.val); // 访问根节点
}
}
与前序遍历和后序遍历相⽐，代码结构完全⼀致，差别仅仅是递归函数的调⽤顺序。
迭代法
前⾯说过，与中序遍历不同的是，后序遍历在访问完左⼦树向上回退到根节点的时候不是⽴马访问根节点的，⽽是得先去访问右⼦树，访问完右⼦树后在回退到根节点，因此，在迭代过程中要复杂⼀点：

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。