首页 > 代码库 > 【Leetcode】Binary Tree Traversal
【Leetcode】Binary Tree Traversal
把三个二叉树遍历的题放在一起了。
递归写法太简单，就不再实现了，每题实现了两种非递归算法。
一种是利用栈，时间和空间复杂度都是O(n)。
另一种是借助线索二叉树，也叫Morris遍历，充分利用树中节点的空指针域。
先序：
Binary Tree Preorder Traversal
Given a binary tree, return the preorder traversal of its nodes‘ values.
For example:
Given binary tree {1,#,2,3},
1 2 / 3
return [1,2,3].
1 class Solution { 2 public: 3 vector<int> preorderTraversal(TreeNode *root) { 4 vector<int> result; 5 stack<TreeNode *> s; 6 if (root) { 7 s.push(root); 8 } 9 while (!s.empty()) {10 TreeNode *p = s.top();11 s.pop();12 result.push_back(p->val);13 if (p->right) {14 s.push(p->right);15 }16 if (p->left) {17 s.push(p->left);18 }19 }20 return result;21 }22 };
1 class Solution { 2 public: 3 vector<int> preorderTraversal(TreeNode *root) { 4 vector<int> result; 5 TreeNode *p = root; 6 while (p) { 7 if (!p->left) { 8 result.push_back(p->val); 9 p = p->right;10 } else {11 TreeNode *q = p->left;12 while (q->right && q->right != p) {13 q = q->right;14 }15 if (q->right == nullptr) {16 result.push_back(p->val);17 q->right = p;18 p = p->left;19 } else {20 q->right = nullptr;21 p = p->right;22 }23 }24 }25 return result;26 }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].
1 class Solution { 2 public: 3 vector<int> inorderTraversal(TreeNode *root) { 4 vector<int> result; 5 TreeNode *p = root; 6 stack<TreeNode *> s; 7 while (!s.empty() || p != nullptr) { 8 if (p != nullptr) { 9 s.push(p);10 p = p->left;11 } else {12 p = s.top();13 s.pop();14 result.push_back(p->val);15 p = p->right;16 }17 }18 return result;19 }20 };
1 class Solution { 2 public: 3 vector<int> inorderTraversal(TreeNode *root) { 4 vector<int> result; 5 TreeNode *p = root; 6 while (p) { 7 if (p->left) { 8 TreeNode *q = p->left; 9 while (q->right && q->right != p) {10 q = q->right;11 }12 if (q->right == p) {13 result.push_back(p->val);14 q->right = nullptr;15 p = p->right;16 } else {17 q->right = p;18 p = p->left;19 }20 } else {21 result.push_back(p->val);22 p = p->right;23 }24 }25 return result;26 }27 };
后序：
Binary Tree Postorder Traversal
Given a binary tree, return the postorder traversal of its nodes‘ values.
For example:
Given binary tree {1,#,2,3},
1 2 / 3
return [3,2,1].
1 class Solution { 2 public: 3 vector<int> postorderTraversal(TreeNode *root) { 4 vector<int> result; 5 stack<TreeNode *> s; 6 TreeNode *p = root; 7 TreeNode *q = nullptr, *last = nullptr; 8 while (!s.empty() || p) { 9 if (p) {10 s.push(p);11 p = p->left;12 } else {13 q = s.top();14 if (q->right && last != q->right) {15 p = q->right;16 } else {17 result.push_back(q->val);18 s.pop();19 last = q;20 } 21 }22 }23 return result;24 }25 };
1 class Solution { 2 public: 3 vector<int> postorderTraversal(TreeNode *root) { 4 vector<int> result; 5 TreeNode dummy(0); 6 TreeNode *p = &dummy, *pre = nullptr; 7 p->left = root; 8 while (p) { 9 if (p->left == nullptr) {10 p = p->right;11 } else {12 pre = p->left;13 while (pre->right != nullptr && pre->right != p) {14 pre = pre->right;15 }16 if (pre->right == nullptr) {17 pre->right = p;18 p = p->left;19 } else {20 printReverse(result, p->left, pre);21 pre->right = nullptr;22 p = p->right;23 }24 }25 }26 return result;27 }28 29 private:30 void printReverse(vector<int>& v, TreeNode* from, TreeNode *to) {31 reverse(from, to);32 TreeNode *p = to;33 while (true) {34 v.push_back(p->val);35 if (p == from) {36 break;37 }38 p = p->right;39 }40 reverse(to, from);41 }42 43 void reverse(TreeNode *from, TreeNode *to) {44 if (from == to) {45 return;46 }47 TreeNode *x = from, *y = x->right, *z;48 while (true) {49 z = y->right;50 y->right = x;51 x = y;52 y = z;53 if (x == to) {54 break;55 }56 }57 }58 };
【Leetcode】Binary Tree Traversal
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。