aboutsummaryrefslogtreecommitdiff
path: root/binary_tree_preorder.cpp
diff options
context:
space:
mode:
authorjack <[email protected]>2024-06-14 13:13:15 -0600
committerjack <[email protected]>2024-06-14 13:13:15 -0600
commitd343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa (patch)
tree96df922dae2a5073d9a50ea70c7aae6aa37e3ebe /binary_tree_preorder.cpp
downloadleetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.tar.gz
leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.zip
initial
Diffstat (limited to 'binary_tree_preorder.cpp')
-rw-r--r--binary_tree_preorder.cpp28
1 files changed, 28 insertions, 0 deletions
diff --git a/binary_tree_preorder.cpp b/binary_tree_preorder.cpp
new file mode 100644
index 0000000..7bba435
--- /dev/null
+++ b/binary_tree_preorder.cpp
@@ -0,0 +1,28 @@
+#include "leetcode.h"
+
+class Solution {
+public:
+ vector<int> preorderTraversal(TreeNode *root) {
+ // morris traversal
+ vector<int> nodes;
+ while (root) {
+ if (root->left) {
+ TreeNode *pre = root->left;
+ while (pre->right && pre->right != root)
+ pre = pre->right;
+ if (!pre->right) {
+ pre->right = root;
+ nodes.push_back(root->val);
+ root = root->left;
+ } else {
+ pre->right = NULL;
+ root = root->right;
+ }
+ } else {
+ nodes.push_back(root->val);
+ root = root->right;
+ }
+ }
+ return nodes;
+ }
+};