【Android面试】2023最新面试专题三：二叉树篇

public V put(K key, V value) {
    if (table == EMPTY_TABLE) {//如果散列表是空的
        inflateTable(threshold);//会去建一个表
    }
    if (key == null) //hashmap会把key为空的放在数组头部
        return putForNullKey(value);
    int hash = sun.misc.Hashing.singleWordWangJenkinsHash(key);//根据key生成hash值
    int i = indexFor(hash, table.length); //生成散列表中的索引，也就是数组下标
    for (HashMapEntry e = table[i]; e != null; e = e.next) {//遍历链表，看是否存在key值一样的对象，如果有的话就替换value值
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }

    modCount++;
    //如果没找到key值一样的，就添加
    addEntry(hash, key, value, i);
    return null;
}

static int indexFor(int h, int length) {
    // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
    return h & (length-1);
   //为什么长度要是偶数，因为hash值与length的与值不能超过length -1,要不然数组/就越界了，例如hash值是11000111B，length = 1000B,h & (length-1) = 111B,这样得到数组索引肯定不会越界了
}



void resize(int newCapacity) {
    HashMapEntry[] oldTable = table;
    int oldCapacity = oldTable.length;
    if (oldCapacity == MAXIMUM_CAPACITY) {
        threshold = Integer.MAX_VALUE;
        return;
    }
    HashMapEntry[] newTable = new HashMapEntry[newCapacity];//新建一个数组
    transfer(newTable);//完成新旧数组拷贝
    table = newTable;
    threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}

void transfer(HashMapEntry[] newTable) {
    int newCapacity = newTable.length;
    for (HashMapEntry e : table) {//遍历整个数组
        while(null != e) {//将同一个位置的元素按链表顺序取出
            HashMapEntry next = e.next;//先将当前元素指向的下一个元素存起来，一个一个存放到新表的位置中，记住不一定是同一位置，因为长度变了
            int i = indexFor(e.hash, newCapacity);//根据新数组长度，重新生成数组索引
            e.next = newTable[i];//将当前位置的元素链表头指向即将新加入的元素，
            newTable[i] = e;//然后放入数组中，完成同一位置元素链表的拼接，最先添加的元素总在链表末尾
            e = next;//然后继续循环，拿出下一个元素
        }
    }
}

//用来衡量是否要转红黑树的重要参数 
 static final int TREEIFY_THRESHOLD = 8;
 //转红黑树需要的最小数组长度
static final int MIN_TREEIFY_CAPACITY = 64;
 for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        // TREEIFY_THRESHOLD - 1=7，也就是说一旦binCount=7时就会执行下面的转红黑树代码
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }

 final void treeifyBin(Node[] tab, int hash) {
        int n, index; Node e;
        //这里的tab指的是本HashMap中的数组，n为数字长度，如果数组为null或者数组长度小于64
        if (tab == null || (n = tab.length)  hd = null, tl = null;
            do {
                TreeNode p = replacementTreeNode(e, null);
                if (tl == null)
                    hd = p;
                else {
                    p.prev = tl;
                    tl.next = p;
                }
                tl = p;
            } while ((e = e.next) != null);
            if ((tab[index] = hd) != null)
                hd.treeify(tab);
        }
    }

//filename: BinTreeNode.h
template 
void travPre_R(BinTreeNode * root) {//二叉树先序遍历算法（递归版）
    if (!root) return;
    cout data;
    travPre_R(root->LeftChild);
    travPre_R(root->RightChild);
}

template 
void travIn_R(BinTreeNode * root) {//二叉树先序遍历算法（递归版）
    if (!root)
        return;
    travPre_R(root->LeftChild);
    cout data;
    travPre_R(root->RightChild);
}

递归法:
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private List res = new ArrayList();
    public List preorderTraversal(TreeNode root) {
        //中 ——> 左 ——> 右
        preorder(root);
        return res;
    }
    
    private void preorder(TreeNode node){
        if(node == null) return;
        res.add(node.val);
        preorder(node.left);
        preorder(node.right);
    }
}

非递归法：
===基本的算法思想===
创建一个栈，用来储存遍历的轨迹：
1.如果栈不为空则储存当前栈顶元素的值，并弹栈；
2.如果栈顶元素存在右儿子，将右儿子压入；
3.如果栈顶元素有左儿子，将左儿子压入
4.重复1直至栈为空
    
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List preorderTraversal(TreeNode root) {
        List res = new ArrayList();
        Stack stack = new Stack();
        TreeNode cur = root;
        while(cur != null || !stack.isEmpty()){
            if(cur != null){
                res.add(cur.val);
                stack.push(cur);
                cur = cur.left;
            }else{
                cur = stack.pop();
                cur = cur.right;
            }
        }
        return res;
    }
}

递归法:
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private List res = new ArrayList();
    public List inorderTraversal(TreeNode root) {
        inorder(root);
        return res;
    }
    
    public void inorder(TreeNode node){
        if(node == null) return;
        inorder(node.left);
        res.add(node.val);
        inorder(node.right);
    }
}

非递归法：
class Solution {
    public List inorderTraversal(TreeNode root) {
        List res = new ArrayList();
        Stack stack = new Stack();
        TreeNode cur = root;
        while(cur != null || !stack.isEmpty()){
            //压栈
            if(cur != null){
                stack.push(cur);
                cur = cur.left;
            }else{
                //左边已经存完，弹栈
                cur = stack.pop();
                res.add(cur.val);
                cur = cur.right;
            }
        }
        return res;
    }
}

递归法：
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private List res = new ArrayList();
    public List postorderTraversal(TreeNode root) {
        //左右中
        postorder(root);
        return res;
    }
    
    private void postorder(TreeNode node){
        if(node == null) return;
        postorder(node.left);
        postorder(node.right);
        res.add(node.val);
    }
}

非递归法：
基本的算法思想：
使用栈来记录遍历轨迹，并使用一个变量来储存上一次方法的元素，当当前元素左右儿子为空或当前元素已经在上一轮访问过（即上一次方法访问的元素为当前访问元素的节点），则栈顶元素出栈。
class Solution {
    public List postorderTraversal(TreeNode root) {
        List res = new ArrayList();
        if(root == null) return res;
        
        Stack stack = new Stack();
        TreeNode pre = null;
        stack.push(root);
        
        while(!stack.isEmpty()){
            TreeNode cur = stack.peek();
            if((cur.left == null && cur.right == null)
              || (pre != null && (cur.right == pre || cur.left == pre))){
                res.add(cur.val);
                pre = cur;
                stack.pop();
            }else{
                if(cur.right != null) stack.add(cur.right);
                if(cur.left != null) stack.add(cur.left);
            }
        }
        
        return res;
    }
}