leetcode144.二叉树的前序遍历_前序遍历二叉树 leetcode

1：递归实现

 void preTraverse(struct TreeNode* root,int *ret,int* returnSize)
 {
     if(root)
     {
         ret[(*returnSize)++]=root->val;
         preTraverse(root->left,ret,returnSize);
         preTraverse(root->right,ret,returnSize);
     }
 }
int* preorderTraversal(struct TreeNode* root, int* returnSize){
    int *ret=(int *)malloc(sizeof(int)*100);
    *returnSize=0;
    preTraverse(root,ret,returnSize);
    return ret;
}

2：迭代思想

1：因为先序变量是先处理中间的根节点，再处理左子树，再处理右子树，且左子树，右子树也是同样的处理方法。

2：所以我们可以想，能否创建一个栈，先放入右子树，再放入左子树，再放入根节点，这样出栈的时候就可以达到上面的效果。

3：但是根节点可以放入，但左子树和右子树并不知道如何放入，但树只要知道了根节点就可以表示出树中的一切。

4：所以现在只需要放入栈中根节点（表示放入了整棵树）就行，当根节点被操作完以后，根节点出栈，并将用根节点表示的右子树和左子树入栈（一定是右子树先入栈，左子树后入栈，这样才能先处理栈顶的左子树），接着操作栈顶元素ÿ