LeetCode | Binary Tree Preorder Traversal

本文主要是介绍LeetCode | Binary Tree Preorder Traversal，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

先序遍历

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?

先序遍历操作，它要求不用递归做，那就用栈咯
需要注意的是，先序遍历对应着根-左-右，所以压栈的时候先压入右孩子~

一次写对~嘿嘿，继续加油
另外，在这篇博文的最后，有必要对数组转树进行一个总结，从而可以在本地方便地调试

/*** 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;if(root==NULL) return result;//递归的形式//preorder(result,root);//非递归，使用栈stack<TreeNode*> Q;Q.push(root);while(!Q.empty()){TreeNode* node=Q.top();Q.pop();result.push_back(node->val);if(node->right) Q.push(node->right);if(node->left) Q.push(node->left);}return result;}void preorder(vector<int> &result,TreeNode* root){result.push_back(root->val);if(root->left) preorder(result,root->left);if(root->right) preorder(result,root->right);}
};

本地化调试，使用数组初始化一个树

有几点需要说明一下：
数组的元素需要是连续的，于是传入一个vector和pos进行遍历。
根据二叉树的性质，我们可以使用 2*pos+1 和 2*pos+2来表示左右孩子的下标~
通过判断下标合法性来判断是否继续生成孩子节点。

而在开始的地方，需要判断arr[pos]==’#’，以便对中间产生的空左右孩子进行处理

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h> 
#include<string.h>
#include<stdlib.h>
#include<vector>
#include<stack>
using namespace std;struct TreeNode {int val;TreeNode *left;TreeNode *right;TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};//初始化树 
TreeNode* initTree(vector<int> arr,int pos){if(arr[pos]=='#')return NULL;TreeNode* node=new TreeNode(arr[pos]);int lc=2*pos+1;int rc=2*pos+2;if(lc>=arr.size())node->left=NULL;else node->left=initTree(arr,lc);if(rc>=arr.size())node->right=NULL;else node->right=initTree(arr,rc);return node;
}//输出整个树 
void outTree(TreeNode* root) {if(root!=NULL) {printf("%d ",root->val);outTree(root->left);outTree(root->right);}
}class Solution {
public:vector<int> postorderTraversal(TreeNode* root) {vector<int> result;if(root==NULL) return result;
//        
//        postorder(root,result);//非递归，使用栈stack<TreeNode*> Q;Q.push(root);while(!Q.empty()){TreeNode* node=Q.top();Q.pop();result.push_back(node->val);if(node->right) Q.push(node->right);if(node->left) Q.push(node->left);}return result;}void postorder(TreeNode* root,vector<int> &result){if(root!=NULL){result.push_back(root->val);postorder(root->left,result);postorder(root->right,result);}}
};int main(){//输入所有数据int a[] = { 1,2,3,4,5,'#',6,'#','#',7,8};vector<int> num(a, a + 11);TreeNode* root;root=initTree(num,0);Solution solution;vector<int> result=solution.postorderTraversal(root);for(int i=0;i<result.size();i++)printf("%d ",result[i]);//  outTree(root);system("pause");return 0;
}