10.Binary Tree(二叉樹)

定義

at most two children node. 最多有兩個子節(jié)點的樹勿侯。

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節(jié)點與其left预侯、right子節(jié)點相比的優(yōu)先順序。
3.BFS (Breadth-first search)
a. Level by level

(1)pre-order
parent->left->right:先打印自己再打印左右子節(jié)點
題目：
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:先打印左子節(jié)點再打印自己最后打印右子節(jié)點
題目：
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:先打印左子節(jié)點再打印右子節(jié)點最后打印自己
題目:
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;
   }
}