94. Binary Tree Inorder Traversal
Medium
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?
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 | //C++ //C++: dfs 0ms /** * Definition for binary tree * 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> res; dfs(root, res); return res; } void dfs(TreeNode* root, vector<int> &res){ if(!root) return; dfs(root->left, res); res.push_back(root->val); dfs(root->right, res); } }; class Solution { public: vector<int> inorderTraversal(TreeNode* root) { vector<int> res; stack<TreeNode*> stk; TreeNode *p = root; while(p||!stk.empty()){ while(p){ stk.push(p); p = p->left; } p = stk.top(); stk.pop(); res.push_back(p->val); p = p->right; } return res; } }; class Solution { public: vector<int> inorderTraversal(TreeNode *root) { vector<int> res; TreeNode *c = root; while(c){ if(c->left){ TreeNode *p = c->left; while(p->right && p->right!=c){ p = p->right; } if(p->right==NULL){ p->right = c; c = c->left; }else{//c == p->right; p->right = NULL; res.push_back(c->val); c = c->right; } }else{ res.push_back(c->val); c = c->right; } } return res; } }; |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 | //Java /** * 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 { List<Integer> ret = new ArrayList(); public List<Integer> inorderTraversal(TreeNode root) { helper(root); return ret; } void helper(TreeNode root){ if(root!=null){ helper(root.left); ret.add(root.val); helper(root.right); } } } |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 | /** * 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) { if(root==null) return new ArrayList<>(); TreeNode p = root; List<Integer> list = new ArrayList<>(); while(p!=null){ if(p.left==null){ list.add(p.val); p = p.right; }else{//p.left!=null TreeNode prev = p.left; while(prev.right!=null && prev.right!=p) prev = prev.right; if(prev.right==null){//first visit the left of p prev.right = p; p = p.left; }else{//second time visit the left of p => we've done with p.left prev.right = null; list.add(p.val); p = p.right; } } } return list; } } |
No comments:
Post a Comment