devbox
笔触狂放9
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

算法：94.实现中序遍历（3种方法：递归、迭代、Morris）Python & Java_中序遍历的递归算法

作者：笔触狂放9 | 2024-05-19 20:05:27

赞

踩

中序遍历的递归算法

 中序遍历：左 -> 中 -> 右

练习地址：94. 二叉树的中序遍历

1、递归法 

Python实现 

  1. # Definition for a binary tree node.
  2. class TreeNode(object):
  3.     def __init__(self, val=0, left=None, right=None):
  4.         self.val = val
  5.         self.left = left
  6.         self.right = right
  7.         
  8.  
  9. class Solution(object):
  10.  
  11.     def dfs(self, root, res):
  12.         if not root:
  13.             return
  14.         self.dfs(root.left, res)
  15.         res.append(root.val)
  16.         self.dfs(root.right, res)
  17.  
  18.     def inorderTraversal(self, root):
  19.         res = []
  20.         self.dfs(root, res)
  21.         return res
  22.  
  23.  
  24. if __name__ == '__main__':
  25.     # 创建一个二叉树
  26.     tree = TreeNode(1)
  27.     tree.left = TreeNode(2)
  28.     tree.right = TreeNode(3)
  29.     tree.left.left = TreeNode(4)
  30.     tree.left.right = TreeNode(5)
  31.     tree.right.right = TreeNode(6)
  32.  
  33.     # 执行中序遍历
  34.     sol = Solution()
  35.     print(sol.inorderTraversal(tree))  # [4, 2, 5, 1, 3, 6]

Java实现

详细的测试代码请参考：算法：Java构建二叉树并递归实现二叉树的前序、中序、后序遍历-CSDN博客

  1. class Solution {
  2.     //中序遍历
  3.     public List<Integer> inorderTraversal(TreeNode root) {
  4.         List<Integer> res = new ArrayList<Integer>();
  5.         inorder(root, res);
  6.         return res;
  7.     }
  8.     public void inorder(TreeNode root, List<Integer> res) {
  9.         if (root == null) {
  10.             return;
  11.         }
  12.         inorder(root.left, res);
  13.         res.add(root.val);
  14.         inorder(root.right, res);
  15.     }
  16. }

2、迭代法

Python实现

  1. # Definition for a binary tree node.
  2. class TreeNode(object):
  3.     def __init__(self, val=0, left=None, right=None):
  4.         self.val = val
  5.         self.left = left
  6.         self.right = right
  7.  
  8.  
  9. class Solution(object):
  10.  
  11.     def inorderTraversal(self, root):
  12.         res = []
  13.         stack = []
  14.         while root or stack:
  15.             while root:  # 先遍历完所有左节点，放入栈中
  16.                 stack.append(root)
  17.                 root = root.left
  18.             root = stack.pop()  # 将当前节点出栈
  19.             res.append(root.val)
  20.             # 将右节点作为根节点重新开始遍历，直到 root 和 栈 都为空为止
  21.             root = root.right  
  22.         return res
  23.  
  24.  
  25. if __name__ == '__main__':
  26.     # 创建一个二叉树
  27.     tree = TreeNode(1)
  28.     tree.left = TreeNode(2)
  29.     tree.right = TreeNode(3)
  30.     tree.left.left = TreeNode(4)
  31.     tree.left.right = TreeNode(5)
  32.     tree.right.right = TreeNode(6)
  33.  
  34.     # 执行中序遍历
  35.     sol = Solution()
  36.     print(sol.inorderTraversal(tree))  # [4, 2, 5, 1, 3, 6]

Java实现

 

  1. class Solution {
  2.     public List<Integer> inorderTraversal(TreeNode root) {
  3.         List<Integer> res = new ArrayList<Integer>();
  4.         if (root == null) {
  5.             return res;
  6.         }
  7.         Deque<TreeNode> stack = new LinkedList<TreeNode>();
  8.         TreeNode node = root;
  9.         while(!stack.isEmpty() || node != null){
  10.             while (node != null) {
  11.                 stack.push(node);
  12.                 node = node.left;
  13.             }
  14.             node = stack.pop();
  15.             res.add(node.val);
  16.             node = node.right;
  17.         }
  18.         return res;
  19.     }
  20. }

3、Morris（莫里斯）遍历法-Python

仔细看代码注释与图解，其实原理很简单。（该方法会改变树的结构）

  1. # Definition for a binary tree node.
  2. class TreeNode(object):
  3.     def __init__(self, val=0, left=None, right=None):
  4.         self.val = val
  5.         self.left = left
  6.         self.right = right
  7.  
  8. '''
  9. 主要思想：从上往下，把每一个节点与其右子树挂到左子树的最右边
  10. 该方法相比前两种方法，主要是节省了空间，空间复杂度从O(n)变成了O(1)
  11. '''
  12. class Solution(object):
  13.  
  14.     def inorderTraversal(self, root):
  15.         res = []
  16.         while root:
  17.             if root.left:  # 如果当前节点存在左子树，则找到其最右边的子节点
  18.                 pre = root.left
  19.                 while pre.right:  # 找到其最右边的子节点
  20.                     pre = pre.right
  21.                 # 把root赋值给temp，把temp的左子树设为空，挂到最右边那个子节点上去
  22.                 temp = root
  23.                 root = root.left  # 此时根结点被挂到子树上了，我们要变更根结点了，该操作不能放到 temp.left = None 后面，否则执行 temp.left = None 时 root.left 也会被置为空
  24.                 temp.left = None
  25.                 pre.right = temp
  26.             else:
  27.                 res.append(root.val)  # 如果当前节点已经是最左边的节点了，则可以输出它的值，并开始遍历右子树了
  28.                 root = root.right
  29.         return res
  30.  
  31.  
  32. if __name__ == '__main__':
  33.     # 创建一个二叉树
  34.     tree = TreeNode(1)
  35.     tree.left = TreeNode(2)
  36.     tree.right = TreeNode(3)
  37.     tree.left.left = TreeNode(4)
  38.     tree.left.right = TreeNode(5)
  39.     tree.right.left = TreeNode(6)
  40.  
  41.     # 执行中序遍历
  42.     sol = Solution()
  43.     print(sol.inorderTraversal(tree))  # [4, 2, 5, 1, 6, 3]

最近又看到 Morris 中序遍历的第二种解法（该方法最终不改变树的结构），提交结果很喜人，在这里分享一下代码： 

  1. # Definition for a binary tree node.
  2. class TreeNode(object):
  3.     def __init__(self, val=0, left=None, right=None):
  4.         self.val = val
  5.         self.left = left
  6.         self.right = right
  7.  
  8.  
  9. class Solution(object):
  10.     def inorderTraversal(self, root):
  11.         res = []
  12.         while root:
  13.             if root.left:
  14.                 tmp = root.left
  15.                 while tmp.right and tmp.right != root:
  16.                     tmp = tmp.right
  17.                 if tmp.right is None:
  18.                     tmp.right = root
  19.                     root = root.left
  20.                 else:
  21.                     pre = root
  22.                     res.append(pre.val)
  23.                     tmp.right = None
  24.                     root = root.right
  25.             else:
  26.                 pre = root
  27.                 res.append(pre.val)
  28.                 root = root.right
  29.         return res
  30.  
  31.  
  32. if __name__ == '__main__':
  33.  
  34.     # 创建一个二叉树
  35.     tree = TreeNode(3)
  36.     tree.left = TreeNode(1)
  37.     tree.right = TreeNode(4)
  38.     tree.right.left = TreeNode(2)
  39.  
  40.     # 执行中序遍历
  41.     sol = Solution()
  42.     print(sol.inorderTraversal(tree))  # [1, 3, 2, 4]

逻辑图： 

图例顺序：从左往右，从上往下 

 其中，pre的指向顺序就是中序遍历的节点顺序。

原理：

如果root已经是最左节点了，则输出root节点值；

如果root的左结点的右节点指向的就是root，那么则输出root节点值。

pre参数可以优化掉：

  1. class Solution(object):
  2.     def inorderTraversal(self, root):
  3.         res = []
  4.         while root:
  5.             if root.left:
  6.                 temp = root.left
  7.                 while temp.right and temp.right != root:
  8.                     temp = temp.right
  9.                 if not temp.right:
  10.                     temp.right = root
  11.                     root = root.left
  12.                 else:  # temp.right == root 的情况
  13.                     res.append(root.val)
  14.                     temp.right = None
  15.                     root = root.right
  16.             else:
  17.                 res.append(root.val)
  18.                 root = root.right
  19.         return res

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/笔触狂放9/article/detail/594427
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号