中国建设网站简州新城土地整改项目,网络游戏开服表,官网建设银行,wordpress 无法打开代码随想录二刷 #xff5c;二叉树 #xff5c;144.二叉树的前序遍历 题目描述解题思路代码实现递归法迭代法 题目描述
144.二叉树的前序遍历
给你二叉树的根节点 root #xff0c;返回它节点值的 前序 遍历。
示例 1#xff1a; 输入#xff1a;root [1,null,2,3] 输… 代码随想录二刷 二叉树 144.二叉树的前序遍历 题目描述解题思路代码实现递归法迭代法 题目描述
144.二叉树的前序遍历
给你二叉树的根节点 root 返回它节点值的 前序 遍历。
示例 1 输入root [1,null,2,3] 输出[1,2,3]
示例 2
输入root [] 输出[]
示例 3
输入root [1] 输出[1]
示例 4 输入root [1,2] 输出[1,2]
示例 5 输入root [1,null,2] 输出[1,2]
提示
树中节点数目在范围 [0, 100] 内-100 Node.val 100
解题思路
递归三部曲
确定递归函数的参数和返回值 因为要打印出前序遍历节点的数值所以参数里需要传入vector来放节点的数值除了这一点就不需要再处理什么数据了也不需要有返回值所以递归函数返回类型就是void代码如下void traversal(TreeNode* cur, vectorint vec)确定终止条件 当前遍历节点空了就直接returnif (cur NULL) return;确定单层递归的逻辑 前序遍历是中左右的循序所以在单层递归的逻辑是要先取中节点的数值代码如下vec.push_back(cur-val);
if (cur-left) vec.push(cur-left, vec);
if (cur-right) vec.push(cur-right, vec);代码实现
递归法
class Solution {
public:void traversal(TreeNode* cur, vectorint vec) {if (cur NULL) return;vec.push_back(cur-val);if (cur-left) traversal(cur-left, vec);if (cur-right) traversal(cur-right, vac);}vectorint preorderTraversal(TreeNode* root) {vectorint result;traversal(root, result);return result;}
};迭代法
// 前序遍历中左右
// 入栈顺序右左中
class Solution {
public:vectorint preorderTraversal(TreeNode* root) {vectorint result;stackTreeNode* st;if (root ! NULL) st.push(root);while (!st.empty()) {TreeNode* node st.top();if (node ! NULL) {st.pop();if (node-right) st.push(node-right);if (node-left) st.push(node-left);st.push(node);st.push(NULL);} else {st.pop();node st.top();st.pop();result.push_back(node-val);}}return result;}
};
