本文共 1705 字，大约阅读时间需要 5 分钟。

二叉树的前序遍历方法

题目

给定一个二叉树，返回其节点值的前序遍历结果。

思路

二叉树的前序遍历（Preorder Traversal）是一种经典的遍历方式，通常分为递归和非递归两种实现方法。递归方法通过递归调用实现，非常直观且简洁。非递归方法则通过使用栈来模拟递归的过程，避免了递归可能带来的栈溢出问题。

递归实现

递归实现前序遍历的思路非常简单明了。我们定义一个递归函数，依次访问根节点，然后递归地访问左子树，最后递归地访问右子树。这种方法的时间复杂度是O(n)，空间复杂度是O(log n)，在大多数情况下是非常高效的。

#include 
   
    
using namespace std;
class Solution {
public:
    vector
    
      preorderTraversal(TreeNode* root) {
        vector
     
       result;
        preorder(result, root);
        return result;
    }
    
    void preorder(vector
      
       & result, TreeNode* root) {
        if (root == nullptr) {
            return;
        }
        result.push_back(root->val);
        if (root->left != nullptr) {
            preorder(result, root->left);
        }
        if (root->right != nullptr) {
            preorder(result, root->right);
        }
    }
};
      
     
    
   

非递归实现

非递归实现通过栈来模拟递归的过程。栈用于存储要访问的节点，确保在处理完右子树后再处理左子树。这种方法的时间复杂度是O(n)，空间复杂度是O(n)，适用于非常深的二叉树。

#include 
   
    
using namespace std;
class Solution {
public:
    vector
    
      preorderTraversal(TreeNode* root) {
        vector
     
       result;
        if (root == nullptr) {
            return result;
        }
        
        stack
      
        s;
        s.push(root);
        
        while (!s.empty()) {
            TreeNode* temp = s.top();
            s.pop();
            result.push_back(temp->val);
            
            if (temp->right != nullptr) {
                s.push(temp->right);
            }
            if (temp->left != nullptr) {
                s.push(temp->left);
            }
        }
        
        return result;
    }
};
      
     
    
   

总结

前序遍历是遍历二叉树的常用方式，两种方法各有优劣。递归实现简单直观，非递归实现则更高效，适合处理大规模数据。选择哪种方法取决于具体需求和性能考虑。

转载地址：http://uaqfk.baihongyu.com/