036二叉树的中序遍历

二叉树的中序遍历题目链接https://leetcode.cn/problems/binary-tree-inorder-traversal/description/?envTypestudy-plan-v2envIdtop-100-liked我的解答public ListInteger inorderTraversal(TreeNode root) { ListInteger ans new ArrayList(); solve(root,ans); return ans; } public void solve(TreeNode root, ListInteger ans){ if(rootnull){ return; } solve(root.left,ans); ans.add(root.val); solve(root.right,ans); }分析代码的时间复杂度为O(n)空间复杂度为O(n)。解题思路采用递归。每次先递归遍历每个节点的左子树再将当前节点加入答案最后递归遍历右子树。中序遍历左根右。看了官方题解后的解答//官方题解的方法一与我的解答思路相同。 //方法二迭代 //时间复杂度O(n) //空间复杂度O(n) public ListInteger inorderTraversal(TreeNode root) { ListInteger ans new ArrayList(); DequeTreeNode stack new LinkedList(); while(root!null || !stack.isEmpty()){ while(root!null){ stack.push(root); rootroot.left; } rootstack.pop(); ans.add(root.val); rootroot.right; } return ans; } //方法三Morris中序遍历 //时间复杂度O(n) //空间复杂度O(1) public ListInteger inorderTraversal(TreeNode root) { ListInteger ans new ArrayList(); //若当前节有左孩子则predecess为当前节点左子树的最右节点 TreeNode predecessornull; while(root!null){ //当前节点有左孩子 if(root.left!null){ //寻找当前节点左子树的最右节点 predecessorroot.left; while(predecessor.right!nullpredecessor.right!root){ predecessorpredecessor.right; } //如果左子树的最右节点不存在右孩子则让root成为predecessor的右孩子 //这样不仅可以标识当前节点的左子树是否已经完成遍历还可以在遍历完成后回到左子树的根节点继续根节点和右子树的遍历 if(predecessor.rightnull){//当前节点的左子树还未遍历过 predecessor.rightroot;//方便左子树遍历完成后回到根节点继续根节点和右子树的遍历 rootroot.left;//移动到左子树进行遍历 } else{//左子树完成遍历收集当前根节点然后继续遍历右子树 ans.add(root.val); predecessor.rightnull;//遍历完当前左子树后还原二叉树 rootroot.right; } } else{//当前节点没有左孩子直接收集当前节点,然后继续遍历右子树 ans.add(root.val); rootroot.right; } } return ans; }分析​ 1、方法二采用迭代用栈模拟递归过程。解题思路当当前节点不为null或者栈不为空不断重复以下过程若当前节点不为空先将当前节点压入栈若当前节点存在左孩子则不断将左孩子加入栈中直到当前节点为null弹出栈顶元素并收集答案当前栈顶节点的左子树已经遍历完成最后遍历弹出的栈顶元素的右子树。​ 2、方法三采用Morris中序遍历。解题思路将每次节点的左子树的最右节点指向当前节点既可以判断当前节点的左子树是否已经遍历过还可以在左子树遍历完成后回到根节点继续根节点和右子树的遍历。​ Morris中序遍历方法的整体步骤如下假设当前遍历到的节点为x​ 若x无左孩子先将x的值加入答案再访问x的右孩子​ 若x有左孩子​ 先找到x左子树的最右节点即左子树中序遍历的最后一个节点x 为中序遍历中的前驱节点我们记为predecessor 根据 predecessor 的右孩子是否为空进行如下操作​ 如果 predecessor 的右孩子为空则将其右孩子指向 x然后访问 x 的左孩子。​ 如果 predecessor 的右孩子不为空则此时其右孩子指向 x说明我们已经遍历完 x 的左子树我们将 predecessor 的右孩子置空将 x 的值加入答案数组然后访问 x 的右孩子。​ 重复上述操作直至访问完整棵树。​ 3、Morris 遍历算法是另一种遍历二叉树的方法它能将非递归的中序遍历空间复杂度降为 O(1)。总结本题主要有三种方法分别为递归、迭代和 Morris 遍历算法。方法三Morris中序遍历比较难理解和想到建议多练习几遍熟悉算法的基本流程。二叉树的中序遍历左根右。