Skip to content

Instantly share code, notes, and snippets.

@c02y
Created May 13, 2020 19:47
Show Gist options
  • Save c02y/403bfb74c56039228f5f3ba0634597c3 to your computer and use it in GitHub Desktop.
Save c02y/403bfb74c56039228f5f3ba0634597c3 to your computer and use it in GitHub Desktop.
TopDownPrintBinaryTree.py
# https://cyc2018.github.io/CS-Notes/#/notes/32.1%20%E4%BB%8E%E4%B8%8A%E5%BE%80%E4%B8%8B%E6%89%93%E5%8D%B0%E4%BA%8C%E5%8F%89%E6%A0%91
class Node:
def __init__(self, val=0):
self.val = val
self.left = None
self.right = None
class TreeNodes:
def __init__(self):
self.root = None
def addNode(self, root, data, index, size):
if index < size:
temp = Node(data[index])
root = temp
root.left = self.addNode(root.left, data, 2 * index + 1, size)
root.right = self.addNode(root.right, data, 2 * index + 2, size)
return root
def PrintFromTopToBottom(self, root):
if not root:
return []
currentStack = [root]
res = []
while currentStack:
nextStack = []
for i in currentStack:
if i.left: nextStack.append(i.left)
if i.right: nextStack.append(i.right)
res.append(i.val)
currentStack = nextStack
return res
if __name__ == '__main__':
data = [1, 2, 3, 4, 5, 6, 7]
tn = TreeNodes()
root = tn.addNode(tn, data, 0, len(data))
res = tn.PrintFromTopToBottom(root)
print(res)
@c02y
Copy link
Author

c02y commented May 13, 2020

CPP version:

// https://cyc2018.github.io/CS-Notes/#/notes/32.1%20%E4%BB%8E%E4%B8%8A%E5%BE%80%E4%B8%8B%E6%89%93%E5%8D%B0%E4%BA%8C%E5%8F%89%E6%A0%91
// https://www.gormanalysis.com/blog/making-a-binary-search-tree-in-cpp/
#include <iostream>
#include <vector>
#include <queue>

// NOTE: TreeNode inside struct TreeNode
struct TreeNode {
	int val;
	TreeNode *left;
	TreeNode *right;
	TreeNode(int x)
		: val(x), left(NULL), right(NULL)
	{
	}
};

std::vector<int> res;
TreeNode *nodes;

class Solution {
public:
	std::vector<int> PrintFromTopToBottom(TreeNode* root) {
		if(root == NULL)
			return res;
		std::queue<TreeNode*> que;
		que.push(root);
		while (!que.empty()) {
			res.push_back(que.front()->val);
			if (que.front()->left != NULL)
				que.push(que.front()->left);
			if (que.front()->right != NULL)
				que.push(que.front()->right);
			que.pop();
		}
		return res;
	}
};

class TreeNodes : public Solution
{
public:
	TreeNodes()
	{
	}

    // https://www.geeksforgeeks.org/construct-complete-binary-tree-given-array/
	TreeNode *addNode(TreeNode *root, int data[], int index, int size)
	{
		if (index < size) {
			TreeNode * temp = new TreeNode(data[index]);
			root = temp;
			// NOTE: root->left/right is parameter and return value at the same time
			root->left = addNode(root->left, data, 2 * index + 1, size);
			root->right = addNode(root->right, data, 2 * index + 2, size);
		}
		return root;
	}
};

int main()
{
	TreeNodes tn;
	int data[] = {1, 2, 3, 4, 5, 6, 7};
	// NOTE: nodes is parameter and return value at the same time
	nodes = tn.addNode(nodes, data, 0, sizeof(data) / sizeof(data[0]));

	res = tn.PrintFromTopToBottom(nodes);

	std::cout << "Structure of binary tree:" << std::endl;
	for (auto i : res)
		std::cout << i << std::endl;

	return 0;
}

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment