二叉树的中序遍历（Java）——Morris迭代算法

二叉树的中序遍历

题目.png

//节点的数据结构
  Definition for a binary tree node.
  public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
} 

对于此题而言，若采用递归算法（简单），我们使用深度优先算法来遍历二叉树。若采用迭代算法，我们使用morris算法来遍历二叉树。

1、深度优先算法是根据二叉树的路径进行遍历
2、广度优先算法是根据二叉树的层级进行遍历

如何针对二叉树的路径进行遍历呢？

• 使用递归，一直向下寻找，直到没有子节点。

class Solution {
    List<Integer> resList = new ArrayList<Integer>();
    public List<Integer> inorderTraversal(TreeNode root) {
        dfs(root);
        return resList;
    }
    public void dfs(TreeNode root){
        if(root==null)return;
        if(root.left!=null){
            dfs(root.left);
        }
        resList.add(root.val);
        if(root.right!=null){
            dfs(root.right);
        }
    }
}

• 使用迭代，我们采用morris算法，进行中序遍历。

morris算法.png

class Solution {
    List<Integer> resList = new ArrayList<Integer>();
    public List<Integer> inorderTraversal(TreeNode root) {
        morris(root);
        return resList;
    }
    //morris迭代算法
    public void morris(TreeNode root){
        while(root!=null){
            //判断当前节点是否无坐子节点
            if(root.left==null){
                //若没有，则将当前节点加入结果集数组
                resList.add(root.val);
                root = root.right;
            }else{
                //若有，那么找到当前节点在中序遍历中的前序节点记作currentRoot
                TreeNode currentRoot = root.left;
                while(currentRoot.right!=null && currentRoot.right != root){
                    currentRoot=currentRoot.right;
                }
                //找到currentRoot后判断currentRoot的右子节点是否已经指向当前节点root
                if(currentRoot.right == root){
                    //若指向，则将root加入结果集数组，并断开链接
                    //进入次步骤证明当前节点的左子节点已全部遍历完成，进入右子节点
                    resList.add(root.val);
                    currentRoot.right = null;
                    root=root.right;
                }else{
                    //若不指向，则将currentRoot的右子节点指向root。并进入左子节点继续遍历二叉树。
                    currentRoot.right = root;
                    root = root.left;
                }
            }
        }
    }
}