1回答

liuyubobobo

2022-10-21

可以的。但是你现在的这个代码的结构肯定是不行的。

这里的核心是：一定要明白，课程里介绍的这个 stack，是在模拟系统栈。

我们可以写出这个代码的递归代码看一下。以下是我的参考代码（C++）：

class Solution {
public:
    vector<string> binaryTreePaths(TreeNode* root) {
        
        if(root == nullptr) return {};
        
        vector<TreeNode*> path;
        vector<string> res;
        
        dfs(root, path, res);
        
        return res;
    }
    
private:
    void dfs(TreeNode* node, vector<TreeNode*>& path, vector<string>& res){
        
        // 1) 
        path.push_back(node);
        if(node->left == nullptr && node->right == nullptr){
            string str = to_string(path[0]->val);
            for(int i = 1; i < path.size(); i ++)
                str += "->" + to_string(path[i]->val);
            res.push_back(str);
        }
        
        if(node->left) dfs(node->left, path, res);
        
        if(node->right) dfs(node->right, path, res);
        
        // 2)
        path.pop_back();
    }
};

注意：

1）为了跟踪当前的路径，我们需要设置一个 path，在递归的过程中维护 path。访问一个节点的时候把这个节点推进 path，退出一个节点把这个节点从 path 里拿出去。对应注释 1 和 2。所以，非递归的代码里也需要这个 path，课程里介绍的 stack 是系统栈，不是这个 path。

2）这个递归代码相当于在先序遍历到一个节点的时候和后续遍历一个节点的时候，都做事情了。（对应注释 1 和 2），那么非递归代码在先序和后序也要都做事情。

==========

基于以上分析，以下是我给出的是基于课程代码的非递归算法参考代码（C++）。

注意：

1）path 和 stack 是两回事儿。stack 是模拟系统栈，path 是为了完成算法逻辑的变量。为了区分，在下面的代码中，stack 我叫 command_stack。

2）先序和后序要做不同的事情，所以 command 的类型有三个。在下面的代码中，do 是做先序遍历的事情；pop 是做后序遍历的事情；go 和课程中介绍的一样（做递归调用，即往系统栈中压指令）。

class Solution {

private:
    struct Command{
        string s;   // go, print, pop
        TreeNode* node;
        Command(string s, TreeNode* node): s(s), node(node){}
    };

public:
    vector<string> binaryTreePaths(TreeNode* root) {
        
        if(root == nullptr) return {};
        
        vector<string> res;
        stack<Command> command_stack;
        vector<TreeNode*> path;
        
        command_stack.push(Command("go", root));
        while(!command_stack.empty()){
            Command command = command_stack.top();
            command_stack.pop();
            
            if(command.s == "do"){ // 先序遍历的事情
                path.push_back(command.node);
                if(command.node->left == nullptr && command.node->right == nullptr){
                    string str = to_string(path[0]->val);
                    for(int i = 1; i < path.size(); i ++)
                        str += "->" + to_string(path[i]->val);
                    res.push_back(str);
                }
            }
            else if(command.s == "pop"){ // 后序遍历的事情
                path.pop_back();
            }
            else{
                // 压后续遍历的指令
                command_stack.push(Command("pop", command.node)); 
                
                // 压访问右节点的指令
                if(command.node->right) 
                    command_stack.push(Command("go",command.node->right));
                
                // 压访问左节点的指令
                if(command.node->left) 
                    command_stack.push(Command("go",command.node->left));
                    
                // 压先序遍历的指令
                command_stack.push(Command("do", command.node)); 
            }
        }
        return res;
    }
};

继续加油！：）

0

1

weixin_慕妹5444478

太感谢了，很好理解！

2022-10-21

共1条回复