【leetcode刷题】T126-二叉树的前序遍历

木又AI帮

发布于 2019-07-30 11:26:44

3720

发布于 2019-07-30 11:26:44

文章被收录于专栏：木又AI帮

二叉树类型第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 删除

二叉树