TopDownPrintBinaryTree.py

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)

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;
}