【leetcode刷题】T126-二叉树的前序遍历
二叉树类型第16篇解题报告
leetcode第144题：二叉树的前序遍历
https://leetcode-cn.com/problems/binary-tree-preorder-traversal/
【题目】
给定一个二叉树，返回它的 前序 遍历。
示例:
输入: [1,null,2,3]
1
\
2
/
3
输出: [1,2,3]
进阶: 递归算法很简单，你可以通过迭代算法完成吗？
【思路】
前序遍历的顺序是：根，左，右。(命名根据访问根节点的顺序)
递归遍历很简单，三步：
print(node)
traversal(node->left)
traversal(node->right)
如果要使用栈来实现，首先得访问并存储根节点，接着访问并存储左孩子节点，直到左孩子节点为空，弹出最后一个根节点，访问并存储其右孩子节点，再接着访问并存储左孩子节点，以此类推……
【代码】
python版本
递归
class Solution(object):
def preorderTraversal(self, root):
res = []
self.traversal(root, res)
return res
def traversal(self, node, res):
if node:
res.append(node.val)
self.traversal(node.left, res)
self.traversal(node.right, res)
栈
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def preorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
if not root:
return []
queue = []
res = []
node = root
while True:
while node is not None:
queue.append(node)
res.append(node.val)
node = node.left
if len(queue) > 0:
node = queue.pop().right
else:
break
return res
C++版本
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> res;
if(!root)
return res;
stack<TreeNode*> q;
TreeNode* node = root;
while(true){
while(node){
q.push(node);
res.push_back(node->val);
node = node->left;
}
if(q.size() > 0){
node = q.top()->right;
q.pop();
}else
break;
}
return res;
}
};
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2019-07-24，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读