every staff about binary tree

binarytree.md

Binary Tree

1. Inorder traversal with iterative and recursive solution:

• Iterative solution for level traversal:

  def levelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        res = []
        queue = [root]
        while len(queue):
            t = queue.pop(0)
            res.append(t.val)
            if t.left:
                queue.append(t.left)
            if t.right:
                queue.append(t.right)
        return res
  

• Iterative solution:

  def inorderTraversal(self, root):
          """
          :type root: TreeNode
          :rtype: List[int]
          """
          res, stack = [], []
          while True:
              while root:
                  stack.append(root)
                  root = root.left
              if not stack:
                  return res
              node = stack.pop()
              res.append(node.val)
              root = node.right
  

• Recursive solution:

  void printPostorder(struct node* node)
  {
       if (node == NULL)
          return;
       printPostorder(node->left);
       printPostorder(node->right);
       printf("%d ", node->data);
  }
  
  void printInorder(struct node* node)
  {
       if (node == NULL)
            return;
       printInorder(node->left);
       printf("%d ", node->data);  
       printInorder(node->right);
  }
  
  void printPreorder(struct node* node)
  {
       if (node == NULL)
            return;
       printf("%d ", node->data);  
       printPreorder(node->left);  
       printPreorder(node->right);
  }