All the pictures in this post are coming from the video: 花花酱 LeetCode Binary Trees 二叉树 - 刷题找工作 SP12

Summary

This page talk about the followed information:

  • The definition of a Binary Tree Node
  • Binary Search Tree
  • Balanced Binary Tree
  • Binary Tree Traversal
    • Pre-Order
    • In-Order (Important: It have been sorted)
    • Post-Order
  • How to create a BST
  • Key To Tree Problems: Recursion
  • Templates:
    • Single root/Two rootse
    • Time Complexity: O(n) / Space Complexity: O(hight)

For the Space Complexity, it may be equal to n if this tree only have the left node or right node.

Definition of a Binary Tree Node

There are some tips for the definition of a Binary Tree Node:

  • You need build your own destruction function for the Struct TreeNode because the C++ new the Tree in the head. So there may be memory leak.
  • This destruction function will delete all node in the tree by Recursion way. For example, when you delete the root node, it will run delete left firstly. After that, it will delete all the children node for the left node.

　如果使用图的思想来看待这一个树的结构的话，那这就是一个有向，无环的图形． 树可以有很多个子节点, 但是二叉树最多只能有一个左孩子和一个右孩子.

The tree have the structure in logic like the above, but how the tree saved in the memory. Is it also like a tree graph? Of course, it isn't. The structure of the tree in the memory like the followed graph.

In the memory, the tree's data are unordered. There is a point in the stack to find the root of the tree in the memory. So, if you want use a tree to sort the data, it is not effective because the tree's data is not continuous in the memory.

How to do the Binary Tree Traversal

If you want to do the preorder for the tree, the function will use the point for the root node which is saved in the stack to find the left node firstly and push the left node information in the stack. After that, deal with the right side. Like the above graph shows. When they finish one part, then pop the node in the stack.

If you lose the root point in the stack, then no one can deal with the tree's data in the memory. This is a memory leak for c++;

Binary Search Tree

We want use a Binary Search Tree to do some element search work, so we hope the Binary Search tree is also a balanced tree. Because it may work faster than the tree like the first picture even though it is also a Binary search tree.

Time Complexity

  • O(h)
  • worst case: O(h) = O(n)
  • Best case: O(h) = O(log(n))

Balanced Binary Tree

The height of left / right substrees are at most 1

So, not all Balanced Binary Tree can be used for the BST. We often want find a perfect BST in the balanced Tree to do some search work. ( O(h) = O(log n) )

Tree Traversal

After we get a Good BST, we can use this tree to do the tree traversal.

The preorder, inorder, postorder are the recursion function. There is just one different feature for these three method. It is when the function to handle the root node in the tree.

In this part, when you change the function print, you can deal with the root node as the order of the output array.

For a BST tree, the inorder function can give a sorted array as the output data.

We often use the inorder tree with the BST tree because the BST have this feature to get a sorted array data after the inorder function.

For the first line, all of them is the code to deal with the boundary for the recursion function. This is a feature for the recursion function.

How to Create a BST

In this funciton, the recursion function is the insert function. In this function, there are a few works we need to do:

  • Deal with the boundary. If the root == null, it build a now node and add this node for it's father left node or right node.
  • To make the decision whether we need to go through the left way or right way.
  • After finish this part, return the root node.

This part is talking about how to create an unbalanced BST. However, most times, we hope we can build a balanced BST to do the search work. (Deal with their height.)

Key to solve the tree problem.

There is a different way to solve the tree problem, you need to think about it as the recursive way.

When you solve the tree problem, you need to think about how to use the left subtree output and the right-subtree output to build the output for question. (How you can use the recursive function return value to solve the problem.) Use the recursive way to think about this question.

Templates

Template 1: One root

There are four steps for this template:

  1. Boundary conditions.
  2. Deal with the root value.
  3. recursive call funciton
  4. compare ouput value

There are some problems like the followed.

The Depth of Binary Tree (Leetcode 104)

public int maxDepth(TreeNode root) {
    if (root == null) return 0;
    return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}

Balanced Binary Tree(Leetcode 110)

```java java private boolean result = true;

public boolean isBalanced(TreeNode root) { maxDepth(root); return result; }

public int maxDepth(TreeNode root) { if (root == null) return 0; int l = maxDepth(root.left); int r = maxDepth(root.right); if (Math.abs(l - r) > 1) result = false; return 1 + Math.max(l, r); } ```

The Diameter of Binary Tree(Leetcode 543)

Template 2: Two root

There are four steps for this template:

  1. Boundary conditions.
  2. Deal with the root value, it may fit with some conditions.
  3. recursive call funciton
  4. compare ouput value

Tree Problems

1.Binary Tree Traversal

树的遍历有两种: 深度优先遍历和宽度优先遍历。 深度优先遍历又可以分为两种：先根遍历和后根遍历。

  • 树的先根遍历是：先访问树的根节点，然后依次先根遍历根的各个子树。树的先根遍历的结果与对应二叉树的先序遍历的结果是相同的。
  • 数的后根遍历是： 先依次后根遍历树根的各个子树，然后访问根结点。树的后根遍历的结果与对应二叉树的后根遍历的结果是相同的。

在深度遍历里面有下面几种情况：

  • 前序遍历：根结点 ---> 左子树 ---> 右子树
  • 中序遍历：左子树---> 根结点 ---> 右子树
  • 后序遍历：左子树 ---> 右子树 ---> 根结点

使用下图作为一个例子：

  • 前序遍历: A->B->C->D->E->F->G->H->I->J->K->M->L
  • 中序遍历: C->B->E->D->F->A->H->G->J->I->M->K->L
  • 后序遍历: C->E->F->D->B->H->J->M->L->K->I->G->A

有以下这些问题:

2.Build Binary Tree

3. Binary search Tree

4. Recursion (Binary Tree)

By guozetang            Updated： 2020-09-19 13:02:30

results matching ""

    No results matching ""