给定一个二叉树,返回它的 前序 遍历。
示例:
输入: [1,null,2,3]
1 \ 2 / 3输出: [1,2,3]
进阶: 递归算法很简单,你可以通过迭代算法完成吗?来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/binary-tree-preorder-traversal递归:
1 /** 2 * Definition for a binary tree node. 3 * struct TreeNode { 4 * int val; 5 * TreeNode *left; 6 * TreeNode *right; 7 * TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8 * }; 9 */10 class Solution {11 public:12 13 void process(TreeNode* root,vector &ans)14 {15 ans.push_back(root->val);16 if(root->left) process(root->left,ans);17 if(root->right) process(root->right,ans);18 }19 20 vector preorderTraversal(TreeNode* root) {21 vector ans;22 if(root)23 process(root,ans);24 return ans;25 }26 27 28 };
迭代:
1 /** 2 * Definition for a binary tree node. 3 * struct TreeNode { 4 * int val; 5 * TreeNode *left; 6 * TreeNode *right; 7 * TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8 * }; 9 */10 class Solution {11 public:12 13 14 vector preorderTraversal(TreeNode* root) {15 vector ans;16 if(!root) return ans;17 stacknodeStack;18 nodeStack.push(root);19 while(!nodeStack.empty()) {20 TreeNode* node = nodeStack.top();21 ans.push_back(node->val);22 nodeStack.pop();23 if(node->right) nodeStack.push(node->right);24 if(node->left) nodeStack.push(node->left);25 }26 return ans;27 }28 29 30 };