10.Binary Tree(二叉树)

定义

at most two children node. 最多有两个子节点的树。

image.png

基本知识点

1.LinkedList可以看成是Binary Tree的变种形式。
2.DFS （Depth-first search）
a. Pre-order: parent before children
b. In-order: parent in the middle of children
c. Post-order: parent after children
这里的pre、in、post词根就是root节点与其left、right子节点相比的优先顺序。
3.BFS (Breadth-first search)
a. Level by level

(1)pre-order
parent->left->right:先打印自己 再打印左右子节点
题目：
Implement an iterative, in-order traversal of a given binary tree, return the list of keys of each node in the tree as it is in-order traversed.
Examples
5
/
3 8
/ \
1 4 11
In-order traversal is [1, 3, 4, 5, 8, 11]
Corner Cases
What if the given binary tree is null? Return an empty list in this case.

/**
 * public class TreeNode {
 *   public int key;
 *   public TreeNode left;
 *   public TreeNode right;
 *   public TreeNode(int key) {
 *     this.key = key;
 *   }
 * }
 */
public class Solution {
  public List<Integer> inOrder(TreeNode root) {
    List<Integer> list = new ArrayList<>();
    if(root == null)return list;
    inOrder(root, list);
    return list;
  }
  
  private void inOrder(TreeNode root, List<Integer> list){
      if(root == null){
        return;
      }
      inOrder(root.left, list);
      list.add(root.key);
      inOrder(root.right, list);
  }
}

(2)in-order
left->parent->right:先打印左子节点 再打印自己 最后打印右子节点
题目：
Implement an iterative, pre-order traversal of a given binary tree, return the list of keys of each node in the tree as it is pre-order traversed.
Examples
5
/
3 8
/ \
1 4 11
Pre-order traversal is [5, 3, 1, 4, 8, 11]
Corner Cases
What if the given binary tree is null? Return an empty list in this case.

/**
 * public class TreeNode {
 *   public int key;
 *   public TreeNode left;
 *   public TreeNode right;
 *   public TreeNode(int key) {
 *     this.key = key;
 *   }
 * }
 */
public class Solution {
  public List<Integer> preOrder(TreeNode root) {
    List<Integer> list = new ArrayList<>();
    preOrder(root, list);
    return list;
  }
  
  private void preOrder(TreeNode root, List<Integer> list){
    if(root == null) return;
    list.add(root.key);
    preOrder(root.left, list);
    preOrder(root.right, list);
  }
}

(3)post-order
left->right->parent:先打印左子节点 再打印右子节点 最后打印自己
题目:
Implement an iterative, post-order traversal of a given binary tree, return the list of keys of each node in the tree as it is post-order traversed.
Examples
5
/
3 8
/ \
1 4 11
Post-order traversal is [1, 4, 3, 11, 8, 5]
Corner Cases
What if the given binary tree is null? Return an empty list in this case.

/**
 * public class TreeNode {
 *   public int key;
 *   public TreeNode left;
 *   public TreeNode right;
 *   public TreeNode(int key) {
 *     this.key = key;
 *   }
 * }
 */
public class Solution {
  public List<Integer> postOrder(TreeNode root) {
    List<Integer> list = new ArrayList<>();
    postOrder(root, list);
    return list;
  }
  
  private void postOrder(TreeNode root, List<Integer> list){
    if(root == null) return;
    postOrder(root.left, list);
    postOrder(root.right, list);
    list.add(root.key);
  }
}

基本概念

• Height of binary tree:The distance between the root wirh the deepest leaf node.

• Level of binary tree: ...

• Balanced binary tree: is commonly defined as a binary tree in which the depth(also known as height) of the left and right subtrees of every node differ by 1 or less.

  1. foreach of the nodes in this binary tree

  2. satisfy: the height of leftsubtree, rightsubtree at most diff by 1.

     
     image.png

• complete binary tree: is a binary tree in which every level, except possibly the last, is completely filled,and all nodes are as far left as possible.

  
  image.png

• Full binary tree:A full binary tree(somtimes proper binary tree or 2-tree) is a tree in which every node other than the leaves has two children.

  
  image.png

• Binary Search Tree: for every single node in the tree, the values in its left subtree ars all smaller than(or equal to) its value, and the values in its right subtree are all larger than (or equal to) its value.

  
  image.png

习题

1.Height of Binary Tree

/**
 * public class TreeNode {
 *   public int key;
 *   public TreeNode left;
 *   public TreeNode right;
 *   public TreeNode(int key) {
 *     this.key = key;
 *   }
 * }
 */
public class Solution {
   public int findHeight(TreeNode root) {
     if(root==null)return 0;
     int leftHeight = findHeight(root.left);
     int rightHeight = findHeight(root.right);
     return Math.max(leftHeight, rightHeight)+1;
   }
}

Time Complexity：
- Each function call (this level): O(1)
- There are in total O(n) function calls
- Summary: O(n)

Space Complexity:
- O(height), height= O(lgn)~O(n)
- Worst case:O(n), like linked list
- On average: O(lgn)

2.Count Node

/**
 * public class TreeNode {
 *   public int key;
 *   public TreeNode left;
 *   public TreeNode right;
 *   public TreeNode(int key) {
 *     this.key = key;
 *   }
 * }
 */
public class Solution {
   public int countNodes(TreeNode root) {
     if(root==null)return 0;
     int leftcount = countNodes(root.left);
     int rightcount = countNodes(root.right);
     return rightcount +rightcount +1;
   }
}

Time Complexity：
- Each function call (this level): O(1)
- There are in total O(n) function calls
- Summary: O(n)

Space Complexity:
- O(height), height= O(lgn)~O(n)
- Worst case:O(n), like linked list
- On average: O(lgn)