LeetCode 之 Binary Tree Preorder Traversal（树）-蒲公英云

LeetCode 之 Binary Tree Preorder Traversal（树）

水深无声 2022-08-02 14:46 197阅读 0赞

【问题描述】

Given a binary tree, return the preorder traversal of its nodes’ values.For example:

Given binary tree {1,#,2,3},

return [1,2,3] .

Note: Recursive solution is trivial, could you do it iteratively?

1.【基础知识】

递归和迭代的区别？

递归及函数调用本身；迭代即循环，循环体中存在自变。

详见：C++ 迭代与递归浅析

详址：http://blog.csdn.net/u013630349/article/details/47036459

2.【屌丝源码】

class Solution {
public:
    int longestValidParentheses(string s) {
        int start = s.find('(');
        // 没有正括号
        if(start<0)
            return 0;
        // 如果字符串只有一个元素 
        string mystr = s.substr(start,s.size()-start);
        if(s.size()<=1)
            return 0;
        stack<char> mystack;
        int i(0),max(0),count(0),j(0);
        while(i<=mystr.rfind('('))        
        {
            int a[100];
            for(j=0;j<mystr.size(),j++)
        }        
    }
};

实现失败！
一直在思考递归是怎么做得，如何模仿，因此，出现如下问题和对策。

1.如何保存变量——静态变量；

2.如何实现静态变量的赋值——类外；

3.到底是给注释中数据结构的二叉树还是给题目中数组——按数据结构来。

卡壳的地方：

如果树为空，如果到达叶子，返回什么？

迭代实现，问题在于，终止条件和层次中的迭代处理方式？

3.【AC源码】

/**
 * 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> result;
        const TreeNode *p;
        stack<const TreeNode *> s;
        p = root;
        if (p != nullptr) s.push(p);
        while (!s.empty()) {
            p = s.top();
            s.pop();
            result.push_back(p->val);
            if (p->right != nullptr) s.push(p->right);
            if (p->left != nullptr) s.push(p->left);
        }
        return result;
    }
};

4.【复盘】

1）不去调试谈什么实现？

不管能不能实现，基本的框架先要给出来，给自己一个可以调试的框架，不盲目写代码不等于代码不写，代码肯定要写，只是说不能实现的时候盲目冒进！

2）简单问题复杂化是思想上的不开动和知识上的不熟悉！

一般问题先考虑不用数据结构行不行，不行的话用数据结构用什么结构合理，像树这种东西就是往下走，不会把结构往复杂的图之流了去，队列、栈、线性表轮着过一遍，答案就出来了。

5.【算法核心思想】