leetcode94 二叉树的中序遍历

小灰灰 2023-06-17 11:51 1阅读 0赞

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9mYW50aWFuenVvLmJsb2cuY3Nkbi5uZXQ_size_16_color_FFFFFF_t_70][]

给定一个二叉树，返回它的中序 遍历。

示例:

输入: \[1,null,2,3\]  
1  
\\  
2  
/  
3

输出: \[1,3,2\]  
进阶: 递归算法很简单，你可以通过迭代算法完成吗？

# 递归 #

# 压栈 #

public class Solution {
        public List < Integer > inorderTraversal(TreeNode root) {
            List < Integer > res = new ArrayList < > ();
            Stack < TreeNode > stack = new Stack < > ();
            TreeNode curr = root;
            while (curr != null || !stack.isEmpty()) {
                while (curr != null) {
                    stack.push(curr);
                    curr = curr.left;
                }
                curr = stack.pop();
                res.add(curr.val);
                curr = curr.right;
            }
            return res;
        }
    }

# morris #

虽然是空间O(1),但是oj并没有测出来效果，依旧空间只超过40%

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    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;
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9mYW50aWFuenVvLmJsb2cuY3Nkbi5uZXQ_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191128191608400.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9mYW50aWFuenVvLmJsb2cuY3Nkbi5uZXQ=,size_16,color_FFFFFF,t_70