LeetCode 94. Binary Tree Inorder Traversal--二叉树中序遍历--递归，迭代--C++,Python解法

LeetCode 94. Binary Tree Inorder Traversal–二叉树中序遍历–递归，迭代–C++,Python解法

---

LeetCode题解专栏：LeetCode题解 LeetCode 所有题目总结：LeetCode 所有题目总结 大部分题目C++，Python，Java的解法都有。

---

题目地址：Binary Tree Inorder Traversal - LeetCode

---

Given a binary tree, return the inorder traversal of its nodes’ values.

Example:

Input: [1,null,2,3] 1 \ 2 / 3 Output: [1,3,2]

Follow up: Recursive solution is trivial, could you do it iteratively?

---

经典的二叉树中序遍历，有迭代和递归2种做法，递归的比较简单。 Python解法如下：

# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def inorderTraversal(self, root: TreeNode) -> List[int]: def helper(root, l): if root is None: return helper(root.left,l) l.append(root.val) helper(root.right,l) l = [] if root is None: return l helper(root, l) return l

C++解法如下：

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: vector<int> l; void helper(TreeNode *root) { if (root == nullptr) { return; } helper(root->left); l.push_back(root->val); helper(root->right); } vector<int> inorderTraversal(TreeNode *root) { l.clear(); helper(root); return l; } };

---

递归的解法总是比迭代简单，迭代解法如下：

Python解法如下：

# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def inorderTraversal(self, root: TreeNode) -> List[int]: if root == None: return [] l = [] res = [] curr = root while curr != None or l != []: while curr is not None: l.append(curr) curr = curr.left curr = l.pop(-1) res.append(curr.val) curr = curr.right return res

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

C++解法如下：

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: vector<int> inorderTraversal(TreeNode *root) { vector<int> result; stack<TreeNode *> l; if (root == nullptr) { return result; } TreeNode *curr = root; while (curr != nullptr || !l.empty()) { while (curr != nullptr) { l.push(curr); curr = curr->left; } curr = l.top(); l.pop(); result.push_back(curr->val); curr = curr->right; } return result; } };