- Summary
- Definition of a Binary Tree Node
- Binary Search Tree
- Balanced Binary Tree
- Tree Traversal
- How to Create a BST
- Key to solve the tree problem.
- Templates
- Tree Problems
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 theC++ 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:
- Boundary conditions.
- Deal with the root value.
- recursive call funciton
- 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:
- Boundary conditions.
- Deal with the root value, it may fit with some conditions.
- recursive call funciton
- 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
有以下这些问题:
Preorder, Inorder, Postorder, N-arr Tree Preorder, N-arr Tree Postorder 方案: 递归或使用堆栈的非递归实现, 而多个子节点的实现,只需要将其装换为循环递归调用即可.
Level Order, Level Order II, Zigzag Level Order, Vertical Order, N-arr Tree Level Order
- Recover Binary Search Tree
- Same Tree
- Symmetric Tree
- Balanced Binary Tree
- Flatten Binary Tree to Linked list
- Population Next Right Pointers in Each Node II
2.Build Binary Tree
3. Binary search Tree
- Unique Binary Search Trees
- Unique Binary Search Trees II
- Validate Binary Search Tree
- Covert Sorted Array to Binary Search Tree)
- Convert Sorted List to Binary Search Tree