LeetCode -****Binary Tree Inorder Traversal 두 갈래 나무의 중서 범람

Given a binary tree, return the inorder traversal of its nodes' values.
For example: Given binary tree  {1,#,2,3} ,
   1
    \
     2
    /
   3

return  [1,3,2] .
Note: Recursive solution is trivial, could you do it iteratively?
제목에서도 귀속은 매우 간단하다는 것을 표시하기 때문에 우리도 귀속과 비귀속의 방식으로 해답을 한다.
프로그램이 VS 프로젝트에서 컴파일됨
#include<iostream>
#include <stdio.h>
#include <vector>
#include <stack>
using namespace :: std;

struct TreeNode
{
	int val;
	TreeNode * left;
	TreeNode * right;
};
TreeNode * CreateBiTree()
{
	char cData;
	scanf_s("%c",&cData);
	getchar();
	if (cData == '#')
	{
		return NULL;
	}
	else
	{
		TreeNode * Node = (TreeNode *)malloc(sizeof(TreeNode));
		if (Node == NULL)
		{
			return NULL;
		}
		Node->val = cData;
		Node->left = CreateBiTree();
		Node->right = CreateBiTree();
		return Node;
	}
}
//< 
void inorderTraversal(TreeNode *root) {
	if(root == NULL)
	{
		return;
	}
	if(root->left)
	{
		inorderTraversal(root->left);
	}
	printf_s("%c ",root->val);  
	if(root->right)
	{
		inorderTraversal(root->right);
	}
}
//< 
void InOrder(TreeNode * root)
{
	stack<TreeNode *> stackNode;
	if (NULL == root)
	{
		return;
	}
	while (root != NULL || !stackNode.empty())
	{
		while (root != 0)
		{
			stackNode.push(root);
			root = root->left;    //< 
		}
		root = stackNode.top();
		printf_s("%c",root->val);
		stackNode.pop();
		root = root->right;
	}
}
void main()
{
	TreeNode * root = CreateBiTree();
	inorderTraversal(root);
	InOrder(root);
	free(root);
	return;
}

좋은 웹페이지 즐겨찾기