94. 二叉树的中序遍历(Binary Tree Inorder Traversal)E

英文题目

Given the root of a binary tree, return the inorder traversal of its nodes' values.
Example 1:

Input: root = [1,null,2,3]
Output: [1,3,2]

Example 2:
```
Input: root = []
Output: []
```
Example 3:
```
Input: root = [1]
Output: [1]
```
Example 4:
```
Input: root = [1,2]
Output: [2,1]
```
Example 5:
```
Input: root = [1,null,2]
Output: [1,2]
```
Constraints:
The number of nodes in the tree is in the range [0, 100].
100 <= Node.val <= 100

中文题目

给定一个二叉树的根节点 root ，返回它的中序遍历。
示例 1：

输入：root = [1,null,2,3]
输出：[1,3,2]

示例 2：
```
输入：root = []
输出：[]
```
示例 3：
```
输入：root = [1]
输出：[1]
```
示例 4：
```
输入：root = [1,2]
输出：[2,1]
```
示例 5：

输入：root = [1,null,2]
输出：[1,2]

提示：
树中节点数目在范围 [0, 100] 内
100 <= Node.val <= 100

递归

按照访问左子树-根节点-右子树的顺序遍历
时间复杂度O(n)，其中 n 是二叉树的节点数。每一个节点恰好被遍历一次

空间复杂度O(n)，为递归过程中栈的开销，平均情况下为 O(log⁡ n)，最坏情况下树呈现链状，为 O(n)

# python3: 时间 40 ms, 击败 65.64%; 内存 16.1 MB, 击败 23.75%
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        self.res = []
        self.dfs(root)
        return self.res
    
    def dfs(self, root: Optional[TreeNode]) -> None:
        if not root:
            return
        self.dfs(root.left)
        self.res.append(root.val)
        self.dfs(root.right)

// c++: 时间 0 ms, 击败 100%; 内存 8.1 MB, 击败 80.99%
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        dfs(res, root);
        return res;
    }

    void dfs(vector<int> &res, TreeNode* root) {
        if (root == nullptr) {
            return;
        }
        dfs(res, root->left);
        res.push_back(root->val);
        dfs(res, root->right);
    }
};

// java: 时间 0 ms, 击败 100%; 内存 39.7 MB, 击败 51.87%
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        dfs(res, root);
        return res;
    }

    public void dfs(List<Integer> res, TreeNode root) {
        if (root == null) {
            return;
        }
        dfs(res, root.left);
        res.add(root.val);
        dfs(res, root.right);
    }
}

// go: 时间 0 ms, 击败 100%; 内存 1.9 MB, 击败 100%
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func inorderTraversal(root *TreeNode) []int {
    res := []int{}
    dfs(&res, root)
    return res
}

func dfs(res *[]int, root *TreeNode) {
    if root == nil {
        return
    }
    dfs(res, root.Left)
    *res = append(*res, root.Val)
    dfs(res, root.Right)
}

// javascript: 时间 68 ms, 击败 24.96%; 内存 41 MB, 击败 87.36%
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var inorderTraversal = function(root) {
    let res = [];
    dfs(res, root);
    return res;
};

const dfs = function(res, root) {
    if (root == null) {
        return;
    }
    dfs(res, root.left);
    res.push(root.val);
    dfs(res, root.right);
};

迭代

不断把根节点入栈，并向左子树前进
出栈一个元素，输出，并向右子树前进，再执行上一步

时间复杂度O(n)，空间复杂度O(n)

# python3: 时间 56 ms, 击败 9.29%; 内存 16.1 MB, 击败 12.93%
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []
        res, cur, stack = [], root, []
        while cur or stack:
            while cur:
                stack.append(cur)
                cur = cur.left
            node = stack.pop()
            res.append(node.val)
            cur = node.right
        return res

// c++: 时间 8 ms, 击败 3.61%; 内存 8.2 MB, 击败 51.66%
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        if (root == nullptr) {
            return res;
        }
        TreeNode* cur = root;
        stack<TreeNode*> st;
        while (cur != nullptr || !st.empty()) {
            while (cur != nullptr) {
                st.push(cur);
                cur = cur->left;
            }
            TreeNode* node = st.top();
            st.pop();
            res.push_back(node->val);
            cur = node->right;
        }
        return res;
    }
};

// java: 时间 0 ms, 击败 100%; 内存 39.8 MB, 击败 35.27%
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        TreeNode cur = root;
        Deque<TreeNode> stack = new LinkedList<>();
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode node = stack.peek();
            stack.pop();
            res.add(node.val);
            cur = node.right;
        }
        return res;
    }
}

// go: 时间 0 ms, 击败 100%; 内存 1.9 MB, 击败 77.88%
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func inorderTraversal(root *TreeNode) []int {
    res := []int{}
    if root == nil {
        return res
    }
    cur := root
    stack := []*TreeNode{}
    for cur != nil || len(stack) > 0 {
        for cur != nil {
            stack = append(stack, cur)
            cur = cur.Left
        }
        node := stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        res = append(res, node.Val)
        cur = node.Right
    }
    return res
}

// javascript: 时间 0 ms, 击败 100%; 内存 1.9 MB, 击败 77.88%
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func inorderTraversal(root *TreeNode) []int {
    res := []int{}
    if root == nil {
        return res
    }
    cur := root
    stack := []*TreeNode{}
    for cur != nil || len(stack) > 0 {
        for cur != nil {
            stack = append(stack, cur)
            cur = cur.Left
        }
        node := stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        res = append(res, node.Val)
        cur = node.Right
    }
    return res
}

Morris遍历

同前序遍历，但只在到达左侧节点返回上层时，输出当前节点

时间复杂度O(n)，空间复杂度O(1)

# python3: 时间 40 ms, 击败 65.64%; 内存 15.9 MB, 击败 60.44%
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        res = []
        if not root:
            return res
        cur = root
        while cur:
            curLeft = cur.left
            
            # 当左子树存在，即可建立前驱节点的连接
            if curLeft:
                while curLeft.right and curLeft.right != cur:
                    # 此时curLeft是cur节点中序遍历的前驱节点
                    curLeft = curLeft.right

                if not curLeft.right:
                    # 1.第一次是找前驱节点，并建立连接
                    curLeft.right = cur
                    cur = cur.left # 2.不断向左子树前进
                    continue # 注意，先建立完所有左子树的连接
                else:
                    # 3.此时是已返回了上层节点，再次找到前驱节点
                    # 断开连接
                    curLeft.right = None
            # 到达左侧节点返回上层时，输出当前节点
            res.append(cur.val)
            
            # 2、4.左子树到头了，向右子树前进，有两种可能：
            # 可能是树本身的右子树，也可能是在上面建立起来的到根节点连接
            cur = cur.right
        return res

// c++: 时间 0 ms, 击败 100%; 内存 8 MB, 击败 92.63%
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        if (root == nullptr) {
            return res;
        }
        TreeNode * cur = root;
        while (cur != nullptr) {
            TreeNode * curLeft = cur->left;
            if (curLeft != nullptr) {
                while (curLeft->right != nullptr && curLeft->right != cur) {
                    curLeft = curLeft->right;
                }
                if (curLeft->right == nullptr) {
                    curLeft->right = cur;
                    cur = cur->left;
                    continue;
                } else {
                    curLeft->right = nullptr;
                }
            }
            res.push_back(cur->val);
            cur = cur->right;
        }
        return res;
    }
};

// java: 时间 0 ms, 击败 100%; 内存 39.7 MB, 击败 51.87%
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        TreeNode cur = root;
        while (cur != null) {
            TreeNode curLeft = cur.left;
            if (curLeft != null) {
                while (curLeft.right != null && curLeft.right != cur) {
                    curLeft = curLeft.right;
                }
                if (curLeft.right == null) {
                    curLeft.right = cur;
                    cur = cur.left;
                    continue;
                } else {
                    curLeft.right = null;
                }
            }
            res.add(cur.val);
            cur = cur.right;
        }
        return res;
    }
}

// go: 时间 0 ms, 击败 100%; 内存 1.9 MB, 击败 77.88%
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func inorderTraversal(root *TreeNode) []int {
    res := []int{}
    if root == nil {
        return res
    }
    cur := root
    for cur != nil {
        curLeft := cur.Left
        if curLeft != nil {
            for curLeft.Right != nil && curLeft.Right != cur {
                curLeft = curLeft.Right
            }
            if curLeft.Right == nil {
                curLeft.Right = cur
                cur = cur.Left
                continue
            } else {
                curLeft.Right = nil
            }
        }
        res = append(res, cur.Val)
        cur = cur.Right
    }
    return res
}

// javascript: 时间 64 ms, 击败 48.12%; 内存 41 MB, 击败 85.20%
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var inorderTraversal = function(root) {
    let res = [];
    if (root == null) {
        return res;
    }
    let cur = root;
    while (cur != null) {
        let curLeft = cur.left;
        if (curLeft != null) {
            while (curLeft.right != null && curLeft.right != cur) {
                curLeft = curLeft.right;
            }
            if (curLeft.right == null) {
                curLeft.right = cur;
                cur = cur.left;
                continue;
            } else {
                curLeft.right = null;
            }
        }
        res.push(cur.val);
        cur = cur.right;
    }
    return res;
};

# 94. 二叉树的中序遍历(Binary Tree Inorder Traversal)E

# 英文题目

# 中文题目

# 递归

# 迭代

# Morris遍历

94. 二叉树的中序遍历(Binary Tree Inorder Traversal)E

英文题目

中文题目

递归

迭代

Morris遍历