刷题第4篇：二叉树遍历

• 2020 年 2 月 25 日
• 筆記

题目描述

给定一个二叉树分别写出它们的前序，中序和后序遍历。

解决方法

一、递归法

1、解决思路

在这道题目中，三种遍历方法如果使用递归来进行操作都将会是十分便捷的一种方法。主要是写一个辅助函数，然后按照不同的遍历方法，在适当的位置加入根元素即可。

首先需要定义一个node类，作为后序使用到的节点类

class TreeNode {      int val;      TreeNode left;      TreeNode right;      TreeNode(int x) { val = x; }  }

我们定义的一个测试方法，主要用于后续的测试

public List<Integer> test(TreeNode root) {      List<Integer> ans = new ArrayList<>();      preorderTraversal(root,ans);      return ans;  }

2、代码实现

下面就是三种遍历方式对应的迭代实现方法：

/*  前序遍历   */  private void preorderTraversal(TreeNode root,List<Integer> list){      if (root!=null) {          list.add(root.val);          if (root.left != null) {              helper(root.left, list);          }          if (root.right != null) {              helper(root.right, list);          }      }  }    /*  中序遍历   */  private void inorderTraversal(TreeNode root,List<Integer> list){      if (root!=null) {          if (root.left != null) {              helper(root.left, list);          }          list.add(root.val);          if (root.right != null) {              helper(root.right, list);          }      }  }    /*  后序遍历   */  private void postorderTraversal(TreeNode root,List<Integer> list){      if (root!=null) {          if (root.left != null) {              helper(root.left, list);          }          if (root.right != null) {              helper(root.right, list);          }          list.add(root.val);      }  }

分析上面的迭代代码，我们可以看到三种方法相当于是如出一辙，仅仅是在迭代过程中向list中插入根节点的时机不同而已。这种算法执行时间很短，但是占用的内存较大。

二、莫里斯法

1、解决思路

刷题过程中，在解题区遇到了一种新的遍历算法，名叫莫里斯遍历算法，但是我没有看太明白，只能粘贴出来供大家参考吧！链接如下所示：

作者：LeetCode  链接：https://leetcode-cn.com/problems/binary-tree-inorder-traversal/solution/er-cha-shu-de-zhong-xu-bian-li-by-leetcode/  来源：力扣（LeetCode）  著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

2、代码实现

class Solution {      public List < Integer > inorderTraversal(TreeNode root) {          List < Integer > res = new ArrayList < > ();          TreeNode curr = root;          TreeNode pre;          while (curr != null) {              if (curr.left == null) {                  res.add(curr.val);                  curr = curr.right; // move to next right node              } else { // has a left subtree                  pre = curr.left;                  while (pre.right != null) { // find rightmost                      pre = pre.right;                  }                  pre.right = curr; // put cur after the pre node                  TreeNode temp = curr; // store cur node                  curr = curr.left; // move cur to the top of the new tree                  temp.left = null; // original cur left be null, avoid infinite loops              }          }          return res;      }  }