【LeetCode】94. Binary Tree Inorder Traversal (3 solutions)
LeetCode Tree Binary Solutions Traversal 94
2023-09-11 14:20:27 时间
Binary Tree Inorder Traversal
Given a binary tree, return the inorder traversal of its nodes' values.
For example:
Given binary tree {1,#,2,3}
,
1 \ 2 / 3
return [1,3,2]
.
Note: Recursive solution is trivial, could you do it iteratively?
解法一:递归
/** * 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> ret; if(!root) return ret; inorder(root, ret); return ret; } void inorder(TreeNode* root, vector<int>& ret) { if(root->left) inorder(root->left, ret); ret.push_back(root->val); if(root->right) inorder(root->right, ret); } };
解法二:非递归
使用map记录是否访问过,使用栈记录访问路径,访问过就出栈。
遵循左根右原则。
/** * 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> ret; if(!root) return ret; stack<TreeNode*> stk; unordered_map<TreeNode*, bool> m; stk.push(root); m[root] = true; while(!stk.empty()) { TreeNode* top = stk.top(); if(top->left) { if(m[top->left] == false) { stk.push(top->left); m[top->left] = true; continue; } } ret.push_back(top->val); stk.pop(); if(top->right) { if(m[top->right] == false) { stk.push(top->right); m[top->right] = true; } } } return ret; } };
解法三:非递归,不需要除栈之外的空间
每次新加入节点时,将左子节点(比当前节点小)全部进栈,这样在出栈的时候就不需要再去访问左子节点,
只需要访问右子节点(比当前节点大)
/** * 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> ret; if(root == NULL) return ret; stack<TreeNode*> stk; stk.push(root); TreeNode* cur = root; while(cur->left) { stk.push(cur->left); cur = cur->left; } while(!stk.empty()) { TreeNode* top = stk.top(); stk.pop(); ret.push_back(top->val); if(top->right) { TreeNode* cur = top->right; stk.push(cur); while(cur->left) { stk.push(cur->left); cur = cur->left; } } } return ret; } };
相关文章
- LeetCode:111_Minimum Depth of Binary Tree | 二叉树的最小深度 | Easy
- LeetCode: 102_Binary Tree Level Order Traversal | 二叉树自顶向下的层次遍历 | Easy
- LeetCode:94_Binary Tree Inorder Traversal | 二叉树中序遍历 | Medium
- [LeetCode] Binary Tree Postorder Traversal
- leetcode - Construct Binary Tree from Inorder and Postorder Traversal
- 【LeetCode-面试算法经典-Java实现】【144-Binary Tree Preorder Traversal(二叉树非递归前序遍历)】
- leetcode--Recover Binary Search Tree
- [LeetCode] 108. Convert Sorted Array to Binary Search Tree ☆(升序数组转换成一个平衡二叉树)
- [LeetCode] 99. Recover Binary Search Tree(复原BST) ☆☆☆☆☆
- 73_leetcode_Construct Binary Tree from Inorder and Postorder Traversal
- LeetCode之Binary Tree Level Order Traversal 层序遍历二叉树
- [LeetCode] Flatten Binary Tree to Linked List
- LeetCode——Binary Tree Preorder Traversal
- leetcode 108. Convert Sorted Array to Binary Search Tree
- leetcode 543. Diameter of Binary Tree
- leetcode 606. Construct String from Binary Tree
- leetcode 637. Average of Levels in Binary Tree