Binary (Search) Tree & Divide Conquer

  • Depth/level: whether root to current node or current node to leaf node

Binary Tree -> n-nary Tree

  • For every node, at most two children without cycle

    • 有null挂在末尾，null是终止遍历条件

  • for node:

    • never lost your root

    • when de reference, check null

    • add nulls for every leaf node

  • need to discuss if parent pointer exists, so we could go up;

  • consider middle

  • if n-nary, it is dynamic, which is List TreeNode

class TreeNode<E>{ //TODO: Generics
    //fields
    E val;
    TreeNode left;
    //TreeNode mid;
    //TreeNode parent;
    TreeNode right;
    //ArrayList<TreeNode> children;
    //Array[26] --> hashmap // TrieNode
    
    //constractor
    
    TreeNode(E value){
        this.val = value;
        null;
    }
}

2:29:56 trie的数据结构

lzzwq 判断26个char中他是否存在

check array有没有重复？

  • clarify: type, size

  • if it is set: use hash set

  • if size is too small, we could use trie

    • streaming flow, word count

  • trie 可以用来排序

Binary Tree

  • Binary Search Tree:

    • For every node , all node's value in the left subtree should be less than to root's value, all node's value in the right subtree should be greater than to root's value,

    • TC: worst case: n^2; best: nLog(n)

  • Complete Binary Tree(Heap):

    • For every level, except the last level, it should be filled completely(full binary tree), last level should be filled as left as possible

  • Balanced Binary Tree:

    • For every node, the height difference between left subtree and right subtree should not greater than one

Q1 L144 L94 L145 Tree Traversal

  • PreOrder: root, left, right

  • InOrder: left, root, right

  • PostOrder: left, right, root

use Recursion:

public void inOrder(TreeNode root){
    if(root == null) return;
    
    inOrder(root.left);
    System.output.println(root.val);
    inOrder(root.right);
}

  • 验证 Binary Search Tree

    • use in order, current node value is greater than the previous value

Q2 L104 Maximum Depth of Binary Tree 第十节22:27

Q2.1 Implement getHeight?

  • TC:

    • O(n) --> the tree is balanced or kind of balanced

    • O(n) --> if it is like a single linked list

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

Q2.2 L111 Minimum Depth of Binary Tree 48:22

  • depth: is from root to leaf node

  • 需要考虑单边情况：一边是null 一边不是

    • null这个leaf node 不算leaf nod， 不能以它因为值是零而直接向上反值为零

public int getHeight(TreeNode root){
    if(root == null ) return 0;
    int leftHeight = getHeight(root.left);
    ／／wall
    int rightHeight = getHeight(root.right);
    //do sth
    if(leftHeight == 0 || rightHeight == 0){
        return leftHeight + rightHeight + 1;
    }
    return Math.min(leftHeight,rightHeight)+1;
}

TC: O(n), n the number of the subtree nodes

Q3 L110 Balanced Binary Tree 1:01:48

  • TC: O(nlogn)

    • maybe not n/2 for next level, but we are checking for it is balanced or not.

  • 冗余计算：

public boolean isBalanced(TreeNode root){
    if(root == null) return true;
    int left = getHeight(root.left);
    int right = getHeight(root.right);
    if(Math.abs(left - right) > 1){
        return false;
    }
    return isBalanced(root.left) && isBalanced(root.right); 
}

  • 如果直接比较等于-1, left right返回上来的height may not the height value

  • so we need to check the left right value first

  • TC: O(n)

public int getHeight(TreeNode root){
    if(root == null ) return 0;
    int left = getHeight(root.left);
    int right = getHeight(root.right);
    // do sth
    if(left == -1 || right == -1 || Math.abs(left - right) > 1){
        return -1;
    }
    return Math.max(left,right)+1;
}

Q4 L101 Symmetric Tree 1:46:03

  • 左右两边呈镜面对称

L226 Invert Binary Tree

call first, and then do sth

public TreeNode invertBinaryTree(TreeNode root){
    if(root == null) return root;
    TreeNode leftNode = invertBinaryTree(root.left);
    TreeNode rightNode = invertBinaryTree(root.right);
    root.left = rightNode;
    root.right = leftNode;
    return root;

  1. if left == null && right == null return true

  2. else if right == null || left == null return false

  3. else if left.val != right.val return false

public boolean isSymmetricTree(TreeNode root){
    if(root == null) return true;
    return isSymmetric(root.left, root.right);
}
private boolean isSymmetric(TreeNode left, TreeNode right){
    if(left == null && right == null) return true;
    else if (left == null || right == null) return false;
    else if (left.val != right.val) return false;
    
    return isSymmetric(left.left, right.right) && isSymmetric(left.right, right.left);
}

Q5 L100 Same Tree 2:28:49

private boolean isSame(TreeNode left, TreeNode right){
    if(left == null && right == null) return true;
    else if (left == null || right == null) return false;
    else if (left.val != right.val) return false;
    
    return isSymmetric(left.left, right.left) && isSymmetric(left.right, right.right);
}

5.1 L572 check small binary tree is part / subtree of larger binary tree

private boolean isSymmetric(TreeNode left, TreeNode right){
    if(left == null && right == null) return true;
    else if (left == null || right == null) return true;
    else if (left.val != right.val) return false;
    
    return isSymmetric(left.left, right.right) && isSymmetric(left.right, right.left);
}

Q6 niu a niu

TC:O4^(log(n)) = n^2

private boolean isNiu(TreeNode left, TreeNode right){
    if(left == null && right == null) return true;
    else if (left == null || right == null) return false;
    else if (left.val != right.val) return false;
    
    return isNiu(left.left, right.left) && isNiu(left.right, right.right)||
    isNiu(left.left, right.right) && isNiu(left.right, right.left);
};
}

Binary Search Tree

Q1 L98 Validate Binary Search Tree第十一节

  1. traverse all the nodes;

    1. TC: O(nlog(n)): when call root n, left is n/2, right n/2, total have logn levels

  2. use min max to carry on bound information 9：00

    1. TC:O(n)

    2. from top to bottom recursion

public boolean isBST(TreeNode root){
    //corner case
    retunr is BST(root, Integer.MIN_VALUE, Integer.MAX_VALUE)
       
}
private boolean isBST(TreeNode root, int lowerBound, int upperBound){
    //base case
    
    if(root == null) return true;
    if(root.val >= upperBound || root.val <= lowBound){
        return false;
    }
    return isBST(root.left, lowerBound, root.val) && isBST(root,right. root.val, upperBound);
}

3. use min max// from bottom to top

4. use binary search tree: in-order traversal ascending sequence

S5. Binary Search TreeIterator

Q2 SearchRange in Binary Search Tree 37：20 --> B+ Tree

  • 背景是数据库的索引(index)

    • 正常情况下的文件存储是lisa存储的？没办法有序访问，更无法按照我们所要的要求去访问，所以需要索引。select all id. id上➕索引加快访问速度；快速定位我的object。

    • eg：学生考试成绩，key is student id, value is the score，所存储的地址. it is kind of concept of key value pair 。

    • so we could use binary search tree, id and location. TC: O(1)

  • if it is binary tree, traverse all node then add to a new list.

  • if binary search tree

    • S1:use in-order traversal by recursion, check whether current root's value in the given range; TC:(O(n))

public List<Integer> searchRange(TreeNode root, int k1, int k2){
    List<Integer> ans = new LinkedList<Integer>();
    if(root == null) return ans;
    searchRange(root.left, k1, k2);
    if(k1 <= root.val && root.val <= k2){
        ans.add(root.val);
    }
    searchRange(root.right, k1, k2);  
    return ans; 
}

  • S2: every time when you do recursion to next level, check if you should go that side

    • decide left or not, check if cur.val > min, there may be candidate in the left subtree

    • decide right or not, check, if cur.val < max, there may be candidate in the right subtree

    • TC: [log(n) , O(n)]

public void searchRange(TreeNode root, int min, int max){
    if(root == null) return;
    if(root.val > min){
         searchRange(root.left, k1, k2);
    }
    if(min <= root.val && max >= root.val) print(root.val);
    if(root.val < max){
         searchRange(root.left, k1, k2);
    }  
}

Q3 L270 Closest Binary Search Tree Value 1:08:38

  • use double instead of integer

  • primitive code: initialize the value which root

  • TC:O(log(n))

  • in work use while, use recursion for interview

public int closestValue(TreeNode root, double target){
    if(root == null) throw exception;
    TreeNode cur = root;
    int cloestVal = 0; // can assign to root.val
    while(cur != null){
        if(Math.abs(cur.val - target) <= Math.abs(cloestVal-target)){
            cloestVal = cur.val;  //find距离更近
        }
        if(cur.val < target) cur= cur.right;
        else if(cur.val > target) cur = cur.right;
        else return cur.val; //零的距离最近
    }
    return cloestVal;
}

3.1 find target

public TreeNode findTarget(TreeNode, int target){
    if(root == null) return null;
    TreeNode cur = root;
    while(cur != null){
        if(cur.val == target) return cur;
        
        if(cur.val > target) cur = cur.left;
        else cur = cur.right;
    }
    return null;
}

3.2 find K Closest Binary Search Tree Value

  • post processing时，left right谁小取谁，then left--, right++

Q4 Binary Search vs Binary Search Tree

  • 两种有直接等效关系

PreviousQueue & StackNextHeap & Graph & HashMap

Last updated

Was this helpful?