/ A binary tree node has data, pointer to left child
and a pointer to right node /
struct Node {
int data;
struct Node left, right;
// constructor function
Node(int data) {
this->data = data;
left = right = NULL;
}
};
/ Given a binary tree, print its nodes according to the
"bottom-up" postorder traversal. /
void printPostorder(struct Node* node) {
if(node == NULL) {
return;
}
// first recur on left subtree
printPostorder(node->left);
// then recur on right subtree
printPostorder(node->right);
// now deal with the node
cout << node->data << " ";
}
/ Given a binnary tree, print its node in inorder /
void printInorder(struct Node* node) {
if(node == NULL)
return;
/* first recur on left child */
printInorder(node->left);
/* then print the data of node */
cont << node->data << " ";
/* now recur on right child */
printInorder(node->right);
}
/ Given a binnary tree, print its nodes in preorder /
void printPreorder(struct Node* node) {
if (node == NULL)
return;
/* first print data of node */
cout << node->data << " ";
/* then recur on left subtree */
printPreorder(node->left);
/* now recur on right subtree */
printPreorder(node->right);
}
/ Driver Program to test above function /
int main()
{
struct Node *root = new Node(1);
root->left = new Node(2);
root->right = new Node(3);
root->left->left = new Node(4);
roor->left->right = new Node(5);
cout << "\nPreorder traversal of binary tree is \n";
printPreorder(root);
cout << "\nInorder traversal of binary tree is \n";
printInorder(root);
cout << "\nPostorder traversal of binary tree is \n";
printPostorder(root);
return 0;
}
- Key idea:
- recursion, need to find out the last process, and notice the `return condition` , in above example, no child node is a cutoff condition， so , for no-child node , recursion funciton result is to print itself's value。
- recurison depth equal to the height of binary tree.
_Originally posted by @zwkcoding in https://github.com/zwkcoding/100Days-Of-Leetcode/issues/13#issuecomment-474796005_
recursion version : inorder traversal binary tree
include
using namespace std;
/ A binary tree node has data, pointer to left child and a pointer to right node / struct Node { int data; struct Node left, right; // constructor function Node(int data) { this->data = data; left = right = NULL; } };
/ Given a binary tree, print its nodes according to the "bottom-up" postorder traversal. / void printPostorder(struct Node* node) { if(node == NULL) { return; }
}
/ Given a binnary tree, print its node in inorder / void printInorder(struct Node* node) { if(node == NULL) return;
}
/ Given a binnary tree, print its nodes in preorder / void printPreorder(struct Node* node) { if (node == NULL) return;
}
/ Driver Program to test above function / int main() { struct Node *root = new Node(1); root->left = new Node(2); root->right = new Node(3); root->left->left = new Node(4); roor->left->right = new Node(5);
}