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]<!-- more -->
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
Follow up: Recursive solution is trivial, could you do it iteratively?
Solution
Solution1
应用递归(Recursion)
java
public class BinaryTreeInorderTraversal{ // Using recursiuon! public List<Integer> inorderTraversal(TreeNode root) { ArrayList<Integer> list = new ArrayList<Integer>(); if(root==null){ return list; } helper(list,root); return list; } public void helper(ArrayList<Integer> list, TreeNode node){ if(node.left!=null){ helper(list,node.left); } list.add(node.val); if(node.right!=null){ helper(list,node.right); } }}不说了，递归还是很容易了解的。
Solution2
不应用递归(Without using recursion)
中序遍历非递归借助栈的实现办法。
c++
/* * app:leetcode lang:**c++** * https://leetcode.com/problems/binary-tree-inorder-traversal/ * 4 ms, faster than 43.54 % * Memory Usage: 8.4 MB, less than 63.67 % *//** * 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) return res; stack<TreeNode*> st; TreeNode* node = root; while(node || !st.empty()){ while(node){ st.push(node); node = node->left; } node = st.top(); st.pop(); res.push_back(node->val); node = node->right; } return res; }};javascript
/* * app:leetcode lang:**javascript** * https://leetcode.com/problems/binary-tree-inorder-traversal/ * Runtime: 95 ms, faster than 27.10% * Memory Usage: 38.8 MB, less than 65.00% *//** * 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) { const res = []; if(!root) return res; const st = []; while(root || st.length){ while(root){ st.push(root); root = root.left; } root = st.pop(); res.push(root.val); root = root.right; } return res;};java
public class BinaryTreeInorderTraversal2{ // Without using recursion! public List<Integer> inorderTraversal(TreeNode root) { ArrayList<Integer> list = new ArrayList<Integer>(); Stack<TreeNode> stack = new Stack<TreeNode>(); TreeNode node = root; while(node!=null || !stack.empty()){ if(node!=null){ stack.push(node); node = node.left; }else{ TreeNode p = stack.pop(); list.add(p.val); node = p.right; } } return list; }}Solution3
最优解
Morris traversal
工夫复杂度：O(n)
空间复杂度：O(1)
java
public class BinaryTreeInorderTraversal{ // Morris Traversal ! public List<Integer> inorderTraversal(TreeNode root) { ArrayList<Integer> list = new ArrayList<Integer>(); TreeNode cur = root; while(cur!=null){ if(cur.left==null){ list.add(cur.val); cur = cur.right; }else{ TreeNode pre = cur.left; while(pre.right!=null && pre.right!=cur){ pre = pre.right; } if(pre.right==null){ pre.right = cur; cur = cur.left; }else{ list.add(cur.val); pre.right = null; cur = cur.right; } } } return list; }}总结
递归和非递归的思路应该留神。同时也应该纯熟Morris Traversal。