LeetCode 题解

积跬步，至千里。

二叉树的前序遍历

分类：LeetCode 标签： 栈 树 发布于：2019-10-20 ID：144

题目描述

来源于 https://leetcode-cn.com/

给定一个二叉树，返回它的 前序 遍历。

 示例:

输入: [1,null,2,3]  
   1
    \
     2
    /
   3 

输出: [1,2,3]

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

递归解法：

class Solution {
  public:
    vector<int> inorderTraversal(TreeNode* root){
        vector<int> res;
        traversal(root, res);
        return res;
    }

    void traversal(TreeNode *node, vector<int>& res) {
        if (!node){
            return;
        }
        res.push_back(node->val);
        traversal(node->left, res);
        traversal(node->right, res);
    }
};

基于栈的解法

观察递归解法，递归调用的第一层就访问 node->val，而后遍历 node->left，而 node->right 是保存在调用栈上的，因此在迭代的写法中，需要将 node->right 保存在栈里。

class Solution {
  public:
    vector<int> preorderTraversal(TreeNode *root) {
        vector<int> res;
        stack<TreeNode*> stk;
        if(root){
            stk.push(root);
        }

        while(!stk.empty()){
            TreeNode *node = stk.top();
            stk.pop();
            while(node){
                res.push_back(node->val);
                if(node->right){
                    stk.push(node->right);
                }
                node = node->left;
            }
        }
        return res;
    }
};