LeetCode 之 Binary Tree Preorder Traversal（树）

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

【问题描述】

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

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

1
        \
         2
        /
       3

return `[1,2,3]` .

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

1.【基础知识】

递归和迭代的区别？

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

详见：[C++ 迭代与递归 浅析][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.【算法核心思想】

> 1）初始化Vector，树空直接返回，不为空进入压栈弹栈机制；
> 
> 2）（按从根出发先遍历左子树再遍历右子树的遍历思想），依次循环从根出发，先右子树先入栈左子树后入栈（子树弹栈是和压栈顺序反过来的）；
> 
> 3）栈空停止迭代。

[C_ _]: http://blog.csdn.net/u013630349/article/details/47036459