LeetCode ：中序遍历二叉树(迭代）
本帖最后由 慵懒的勤快孩儿 于 2020-7-5 22:40 编辑若树为空，则空操作返回，否则从根结点开始（注意并不是先访问根结点），中序遍历根结点的左子树，然后是访问根结点，最后中序遍历右子树。
C语言实现：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int* inorderTraversal(struct TreeNode* root, int* returnSize){
struct TreeNode *stack;
int top = -1;
int *result = (int *)malloc(sizeof(int)*100);
int i = 0;
while(true)
{
while(root)
{
stack[++top] = root;
root = root->left;
/*
从根节点遍历左子树，一直遍历到底
并将遍历到的结点存入数组(栈)内备用
*/
}
if(top == -1){
* returnSize = i;
return result;
//top == -1,栈为空，即全部遍历完毕，输出数据
}
root = stack;
result = root->val;
root = root->right;
/*
从左子树最底开始保存结点数据，每次遍历都查看有无右孩子
如果有右孩子，上面执行上面while
如果没有，则接续从stack栈顶弹出结点，将结点val存入数组
*/
}
}
页:
[1]