We read every piece of feedback, and take your input very seriously.
To see all available qualifiers, see our documentation.
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Given a binary tree, flatten it to a linked list in-place.
For example, given the following tree:
1 / \ 2 5 / \ \ 3 4 6
The flattened tree should look like:
1 \ 2 \ 3 \ 4 \ 5 \ 6
算法思路:
方法一:
push
vector
该方法可以通过题目,但是不满足in-place的条件。
in-place
class Solution{ public: void flatten(TreeNode* root){ std::vector<TreeNode*> node_vec; preorder(root, node_vec); for(int i = 1; i < node_vec.size(); i++){ node_vec[i - 1] -> left = NULL; node_vec[i - 1] -> right = node_vec[i]; } } private: void preorder(TreeNode* node, std::vector<TreeNode*> &node_vec){ if(!node){ return; } node_vec.push_back(node); preorder(node -> left, node_vec); preorder(node -> right, node_vec); } };
方法二:
class Solution{ public: void flatten(TreeNode* root){ TreeNode* last = NULL; preorder(root, last); } private: void preorder(TreeNode* node, TreeNode* &last){ if(!node){ return; } if(!node -> left && !node -> right){ last = node; return; } TreeNode* left = node -> left; TreeNode* right = node -> right; TreeNode* left_last = NULL; TreeNode* right_last = NULL; if(left){ preorder(left, left_last); node -> left = NULL; node -> right = left; last = left_last; } if(right){ preorder(right, right_last); if(left_last){ left_last -> right = right; } last = right_last; } } };
The text was updated successfully, but these errors were encountered:
No branches or pull requests
Flatten Binary Tree to Linked List
Given a binary tree, flatten it to a linked list in-place.
For example, given the following tree:
The flattened tree should look like:
算法思路:
方法一:
push
进入vector
;vector
中的节点,将前面的节点的左指针置空,右指针与后面的节点相连。该方法可以通过题目,但是不满足
in-place
的条件。方法二:
The text was updated successfully, but these errors were encountered: