二叉樹

在計算機科學中，二叉樹是每個節(jié)點最多有兩個子樹的樹結(jié)構(gòu)熙宇。通常子樹被稱作“左子樹”和“右子樹”，左子樹和右子樹同時也是二叉樹溉浙。二叉樹的子樹有左右之分烫止，并且次序不能任意顛倒。

二叉排序樹

二叉排序樹戳稽，又稱二叉查找樹馆蠕、二叉搜索樹、B樹惊奇。

二叉排序樹是具有下列性質(zhì)的二叉樹：

• 若左子樹不空荆几，則左子樹上所有結(jié)點的值均小于它的根結(jié)點的值；
• 若右子樹不空赊时，則右子樹上所有結(jié)點的值均大于或等于它的根結(jié)點的值吨铸；
• 左、右子樹也分別為二叉排序樹祖秒。

二叉排序樹

也就是說诞吱，二叉排序樹中，左子樹都比節(jié)點小竭缝，右子樹都比節(jié)點大房维，遞歸定義。

根據(jù)二叉排序樹這個特點我們可以知道抬纸，二叉排序樹的中序遍歷一定是從小到大的咙俩，比如上圖，中序遍歷結(jié)果是：

 1  3  4  6  7  8  13  14  19

二叉樹節(jié)點定義

采用單項鏈表的形式，只從根節(jié)點指向孩子節(jié)點阿趁，子節(jié)點不保存父節(jié)點膜蛔。

/**
 *  二叉樹節(jié)點
 */
class BinaryTreeNode<T> {
    T value;
    BinaryTreeNode leftNode;
    BinaryTreeNode rightNode;
}

創(chuàng)建二叉樹

二叉樹中左右節(jié)點值本身沒有大小之分，所以如果要創(chuàng)建二叉樹脖阵，就需要考慮如何處理某個節(jié)點是左節(jié)點還是右節(jié)點皂股，如何終止某個子樹而切換到另一個子樹。 因此我選擇了二叉排序樹命黔，二叉排序樹中對于左右節(jié)點有明確的要求呜呐，程序可以自動根據(jù)鍵值大小自動選擇是左節(jié)點還是右節(jié)點。

/**
 * 創(chuàng)建二叉樹
 */
public static BinaryTreeNode<Integer> createTreeWithValues(int[] values) {
    BinaryTreeNode root = null;
    for (int value: values) {
        root = addTreeNode(root, value);//添加每一個節(jié)點
    }
    return root;
}
/**
 * 在treeNode中添加值為value的節(jié)點
 */
public static BinaryTreeNode<Integer> addTreeNode(BinaryTreeNode<Integer> treeNode, int value) {
    if (treeNode == null) {
        treeNode = new BinaryTreeNode<>();//創(chuàng)建節(jié)點
        treeNode.value = value;
    } else {
        if (value <= treeNode.value) {//對比左右節(jié)點
            treeNode.leftNode = addTreeNode(treeNode.leftNode, value);
        } else {
            treeNode.rightNode = addTreeNode(treeNode.rightNode, value);
        }
    }
    return treeNode;
}

二叉樹的遍歷

根據(jù)二叉排序樹的定義悍募，我們可以知道在查找某個元素時：

• 先比較它與根節(jié)點蘑辑，相等就返回；或者根節(jié)點為空坠宴，說明樹為空洋魂，也返回；
• 如果它比根節(jié)點小啄踊，就從根的左子樹里進行遞歸查找忧设；
• 如果它比根節(jié)點大刁标，就從根的右子樹里進行遞歸查找颠通。

這就是一個簡單的二分查找。只不過和二分查找還是有些不同的地方的膀懈。

二叉樹的性能取決于二叉樹的層數(shù)：

• 最好的情況是O(logn),存在于完全二叉樹情況下顿锰，其訪問性能近似于折半查找；
• 最差的情況是O(n),比如插入的元素所有節(jié)點都沒有左子樹（右子樹）启搂，這種情況需要將二叉樹的全部節(jié)點遍歷一次硼控。

二叉排序樹

/**
 * 中根遍歷
 */
public static void inOrderTraverseTree(BinaryTreeNode<Integer> rootNode) {
    if (rootNode != null) {
        //左中右，中根遍歷
        inOrderTraverseTree(rootNode.leftNode);
        //中左右胳赌，先根遍歷
        System.out.println(" " + rootNode.value + " ");
        //左右中牢撼，后根遍歷
        inOrderTraverseTree(rootNode.rightNode);
    }
}

這是一斷中根遍歷的代碼，先根遍歷和后根遍歷只是調(diào)整上面幾行代碼的順序而已疑苫。

二叉樹節(jié)點刪除

插入操作和查找比較類似熏版，而刪除則相對復雜一點，需要根據(jù)刪除節(jié)點的情況分類來對待：

• 如果要刪除的節(jié)點正好是葉子節(jié)點捍掺，直接刪除就 Ok 了撼短；
• 如果要刪除的節(jié)點還有子節(jié)點，就需要建立父節(jié)點和子節(jié)點的關(guān)系：

• 如果只有左孩子或者右孩子挺勿，直接把這個孩子上移放到要刪除的位置就好了曲横；
• 如果有兩個孩子，就需要選一個合適的孩子節(jié)點作為新的根節(jié)點不瓶，該節(jié)點稱為 繼承節(jié)點禾嫉。（新節(jié)點要求比所有左子樹要大灾杰、比右子樹要小，我們可以選擇左子樹中的最大節(jié)點夭织，或者選擇右子樹中的最小的節(jié)點吭露。）

/**
 * 二叉樹查找
 */
public static BinaryTreeNode<Integer> search(BinaryTreeNode<Integer> rootNode, int value) {
    if (rootNode != null) {
        if (rootNode.value == value){
            return rootNode;
        }
        if (value > rootNode.value) {
            return search(rootNode.rightNode, value);
        } else {
            return search(rootNode.leftNode, value);
        }
    }
    return rootNode;
}

/**
 * 尋找value節(jié)點的父節(jié)點
 */
public static BinaryTreeNode<Integer> searchParent(BinaryTreeNode<Integer> rootNode, int value) {
    //如果當前節(jié)點為null，或者當前節(jié)點為根節(jié)點尊惰。返回null
    if (rootNode == null || rootNode.value == value) {
        return null;
    } else {
        //當前節(jié)點的左兒子或者右兒子等于value讲竿，則返回當前節(jié)點。
        if (rootNode.leftNode != null && value == (Integer)rootNode.leftNode.value ||
            rootNode.rightNode != null && value == (Integer)rootNode.rightNode.value) {
                return rootNode;
        }
        //判斷需要尋找的節(jié)點的位置弄屡，
        if (value > rootNode.value && rootNode.rightNode != null) {
            return searchParent(rootNode.rightNode, value);
        } else {
            return searchParent(rootNode.leftNode, value);
        }
    }
}

/**
 * 刪除rootNode為根節(jié)點的二叉樹中值為value的節(jié)點
 */
public static BinaryTreeNode<Integer> delete(BinaryTreeNode<Integer> rootNode, int value) {
    //判斷是否刪除的節(jié)點為根節(jié)點
    if (rootNode == null && rootNode.value == value) {
        rootNode = null;
        return rootNode;
    }
    //找到刪除的節(jié)點的父節(jié)點
    BinaryTreeNode<Integer> parentNode = searchParent(rootNode, value);
    //找不到父節(jié)點题禀，表示該二叉樹沒有對應的節(jié)點
    if (parentNode == null) {
        return rootNode;
    }
    BinaryTreeNode<Integer> deleteNode = search(rootNode, value);
    //找不到該節(jié)點
    if (deleteNode == null) {
        return rootNode;
    }
    //需要刪除的節(jié)點，為葉子節(jié)點
    if (deleteNode.leftNode == null && deleteNode.rightNode == null) {
        deleteNode = null;
        if (parentNode.leftNode != null && value == (Integer)parentNode.leftNode.value) {
            parentNode.leftNode = null;
        } else {
            parentNode.rightNode = null;
        }
    }
    //需要刪除的節(jié)點膀捷，只有左子樹迈嘹，左子樹繼承該刪除的位置
    else if (deleteNode.rightNode == null) {
        if (parentNode.leftNode != null && value == (Integer)parentNode.leftNode.value) {
            parentNode.leftNode = deleteNode.leftNode;
        } else {
            parentNode.rightNode = deleteNode.leftNode;
        }
    }
    //需要刪除的節(jié)點，只有右子樹全庸，右子樹繼承該刪除的位置
    else if (deleteNode.leftNode == null) {
        if (parentNode.leftNode != null && value == (Integer)parentNode.leftNode.value) {
            parentNode.leftNode = deleteNode.rightNode;
        } else {
            parentNode.rightNode = deleteNode.rightNode;
        }
    }
    //要刪除的節(jié)點既有左海子秀仲，又有右孩子。需要選擇一個設(shè)施的節(jié)點繼承壶笼，我們選擇左子樹中的最右節(jié)點
    else {
        BinaryTreeNode<Integer> tmpDeleteNode = deleteNode;
        BinaryTreeNode<Integer> selectNode = tmpDeleteNode.leftNode;
        if (selectNode.rightNode == null) {
            selectNode.rightNode = deleteNode.rightNode;
        } else {
            //找到deleteNode的左子樹中的最右節(jié)點神僵，即最大節(jié)點
            while (selectNode.rightNode != null) {
                tmpDeleteNode = selectNode;
                selectNode = selectNode.rightNode;
            }
            //將選出的繼承節(jié)點的左子樹賦值給父節(jié)點的右子樹
            tmpDeleteNode.rightNode = selectNode.leftNode;
            //繼承節(jié)點繼承需要刪除的左右子樹
            selectNode.leftNode = deleteNode.leftNode;
            selectNode.rightNode = deleteNode.rightNode;
        }
        //將選出的繼承節(jié)點進行繼承（刪除對應節(jié)點）
        if (parentNode.leftNode != null && value == (Integer)parentNode.leftNode.value) {
            parentNode.leftNode = selectNode;
        } else {
            parentNode.rightNode = selectNode;
        }
    }
    return rootNode;
}  

測試代碼

public static void main(String[] args) {
    int[] array = new int[]{8,3,19,1,6,14,4,7};
    //創(chuàng)建二叉樹
    BinaryTreeNode root = createTreeWithValues(array);
    //中根遍歷
    inOrderTraverseTree(root);
    System.out.println();
    //插入13
    addTreeNode(root, 13);
    //中根遍歷
    inOrderTraverseTree(root);
    //刪除value=3的節(jié)點
    delete(root, 3);
    System.out.println();
    //中跟遍歷結(jié)果
    inOrderTraverseTree(root);

}

結(jié)果：

 1  3  4  6  7  8  14  19 
 1  3  4  6  7  8  13  14  19 
 1  4  6  7  8  13  14  19 
Process finished with exit code 0

二叉樹的深度

二叉樹深度定義：從根節(jié)點到葉子節(jié)點依次進過的節(jié)點形成樹的一條路徑，最長路徑的長度為樹的深度覆劈。

• 如果根節(jié)點為空保礼，則深度為0；
• 如果左右節(jié)點都為空责语，則深度為1炮障；
• 遞歸思想：二叉樹的深度=max(左子樹的深度，右子樹的深度) + 1坤候；

/**
 * 二叉樹的深度
 */
public static int depthOfTree(BinaryTreeNode<Integer> root) {
    if (root == null) {
        return 0;
    }
    if (root.leftNode == null && root.rightNode == null) {
        return 1;
    }
    int leftDepth = depthOfTree(root.leftNode);
    int rightDepth = depthOfTree(root.rightNode);
    return Math.max(leftDepth, rightDepth) + 1;
}

二叉樹的寬度

/**
 * 二叉樹的寬度：各層節(jié)點數(shù)的最大值
 * @param root 二叉樹的根節(jié)點
 * @return 二叉樹的寬度
 */
public static int widthOfTree(BinaryTreeNode<Integer> root) {
    if (root == null) {
        return 0;
    }
    //當前二叉樹最大寬度=根節(jié)點
    int maxWith = 1;
    int currentWidth = 0;
    //隊列：先進先出胁赢，每次循環(huán)后保留一層樹的某一層的所有節(jié)點
    Queue<BinaryTreeNode<Integer>> list = new LinkedList<>();
    list.add(root);
    while (list.size() > 0) {
        currentWidth = list.size();
        //遍歷當前層的所有節(jié)點，并將所有節(jié)點的子節(jié)點加入到隊列中
        for (int i = 0; i < currentWidth; i++) {
            BinaryTreeNode<Integer> node = list.peek();
            list.poll();
            if (node.leftNode != null) {
                list.add(node.leftNode);
            }
            if (node.rightNode != null) {
                list.add(node.rightNode);
            }
        }
        maxWith = Math.max(maxWith, list.size());
    }
    return maxWith;
}

二叉樹某層中的節(jié)點數(shù)

/**
 * 二叉樹某層中的節(jié)點數(shù)
 * @param rootNode 二叉樹根節(jié)點
 * @param level 層
 * @return level層的節(jié)點數(shù)
 */
public static int numberOfNodesOnLevel(BinaryTreeNode<Integer> rootNode, int level) {
    //二叉樹不存在白筹，或者level不存在的時候節(jié)點數(shù)為0
    int result = 0;
    if (rootNode == null || level < 1) {
        return result;
    }
    //level=1智末，為根節(jié)點，節(jié)點數(shù)為1
    if (level == 1) {
        result = 1;
        return result;
    }
    //遞歸：node為根節(jié)點的二叉樹的level層節(jié)點數(shù) = 
    // node節(jié)點左子樹（level - 1）層的節(jié)點數(shù) + node節(jié)點的右子樹（level - 1）層的節(jié)點數(shù)
    return numberOfNodesOnLevel(rootNode.leftNode, level - 1) +
            numberOfNodesOnLevel(rootNode.rightNode, level - 1);
}

二叉樹的葉子節(jié)點個數(shù)

/**
 * 二叉樹的葉子節(jié)點個數(shù)
 * @param rootNode
 * @return 葉子節(jié)點個數(shù)
 */
public static int numberOfLeafsInTree(BinaryTreeNode<Integer> rootNode) {
    int result = 0;
    if (rootNode == null) {
        return result;
    }
    //rootNode沒有子節(jié)點遍蟋，所以根節(jié)點為葉節(jié)點result=1;
    if (null == rootNode.leftNode && null == rootNode.rightNode) {
        result = 1;
        return result;
    }
    //遞歸：root的葉節(jié)點 = node的左子樹的葉節(jié)點 + node的右子樹的葉節(jié)點
    return numberOfLeafsInTree(rootNode.leftNode) + numberOfLeafsInTree(rootNode.rightNode);
}

二叉樹的最大距離（二叉樹的直徑）

二叉樹中任意兩個節(jié)點都有且僅有一條路徑吹害，這個路徑的長度叫這兩個節(jié)點的距離。二叉樹中所有節(jié)點之間的距離的最大值就是二叉樹的直徑虚青。
有一種解法它呀，把這個最大距離劃分了3種情況：

• 這2個節(jié)點分別在根節(jié)點的左子樹和右子樹上，他們之間的路徑肯定經(jīng)過根節(jié)點，而且他們肯定是根節(jié)點左右子樹上最遠的葉子節(jié)點（他們到根節(jié)點的距離=左右子樹的深度）纵穿。
• 這2個節(jié)點都在左子樹上
• 這2個節(jié)點都在右子樹上
  綜上下隧，只要取這3種情況中的最大值，就是二叉樹的直徑谓媒。

**
 * 二叉樹的最大距離（直徑）
 * @param rootNode 根節(jié)點
 * @return 最大距離
 */
public static int maxDistanceOfTree(BinaryTreeNode<Integer> rootNode) {
    if (rootNode == null) {
        return 0;
    }
    //1淆院、最遠距離經(jīng)過根節(jié)點：距離 = 左子樹深度 + 右子樹深度
    int distance = depthOfTree(rootNode.leftNode) + depthOfTree(rootNode.rightNode);
    //2、最遠距離在根節(jié)點左子樹上句惯，即計算左子樹最遠距離
    int disLeft = maxDistanceOfTree(rootNode.leftNode);
    //3土辩、最遠距離在根節(jié)點右子樹上，即計算右子樹最遠距離
    int disRight = maxDistanceOfTree(rootNode.rightNode);
    return Math.max(distance, Math.max(disLeft, disRight));
}

這個方案效率較低抢野，因為計算子樹的深度和最遠距離是分開遞歸的拷淘，存在重復遞歸遍歷的情況。其實一次遞歸指孤，就可以分別計算出深度和最遠距離启涯，于是有了第二種方案：

class TreeNodeProperty{
    int depth = 0;
    int distance = 0;
}
public static int maxDistanceOfTree2(BinaryTreeNode<Integer> rootNode) {
    if (rootNode == null) {
        return 0;
    }
    return propertyOfTreeNode(rootNode).distance;
}

public static TreeNodeProperty propertyOfTreeNode(BinaryTreeNode<Integer> rootNode) {
    if (rootNode == null) {
        return new TreeNodeProperty();
    }
    TreeNodeProperty left = propertyOfTreeNode(rootNode.leftNode);
    TreeNodeProperty right = propertyOfTreeNode(rootNode.rightNode);
    TreeNodeProperty p = new TreeNodeProperty();
    //當前節(jié)點的樹的深度depth = 左子樹深度 + 右子樹深度 + 1；（根節(jié)點也占一個depth）
    p.depth = Math.max(left.depth, right.depth) + 1;
    p.distance = Math.max(Math.max(left.distance, right.distance), left.depth + right.depth);
    return p;
}

二叉樹中某個節(jié)點到根節(jié)點的路徑

既是尋路問題恃轩，又是查找節(jié)點問題结洼。
定義一個存放路徑的棧（不是隊列了，但是還是用可變數(shù)組來實現(xiàn)的）

• 壓入根節(jié)點叉跛，再從左子樹中查找（遞歸進行的）松忍，如果未找到，再從右子樹中查找昧互，如果也未找到挽铁，則彈出根節(jié)點伟桅，再遍歷棧中上一個節(jié)點敞掘。
• 如果找到，則棧中存放的節(jié)點就是路徑所經(jīng)過的節(jié)點楣铁。

/**
 * 二叉樹中某個節(jié)點到根節(jié)點的路徑
 * @param rootNode 根節(jié)點
 * @param treeNode 節(jié)點
 * @return 路徑隊列
 */
public static Stack<BinaryTreeNode> pathOfTreeNode(BinaryTreeNode<Integer> rootNode, int treeNode) {
    Stack<BinaryTreeNode> pathList = new Stack<>();
    isFoundTreeNode(rootNode, treeNode, pathList);
    return pathList;
}

/**
 * 查找某個節(jié)點是否在樹中
 * @param rootNode 根節(jié)點
 * @param treeNode 待查找的節(jié)點
 * @param path 根節(jié)點到待查找節(jié)點的路徑
 * @return 是否找到該節(jié)點
 */
public static boolean isFoundTreeNode(BinaryTreeNode<Integer> rootNode, int treeNode,
                                      Stack<BinaryTreeNode> path) {
    if (rootNode == null) {
        return false;
    }
    //當前節(jié)點就是需要找的節(jié)點
    if (rootNode.value == treeNode) {
        path.add(rootNode);
        return true;
    }
    //將路過的節(jié)點壓入棧中
    path.add(rootNode);
    //先在左子樹中查找
    boolean find = isFoundTreeNode(rootNode.leftNode, treeNode, path);
    if (!find) {
        //如果沒有找到玖雁，然后在右子樹中查找
        find = isFoundTreeNode(rootNode.rightNode, treeNode, path);
    }
    if (!find) {
        path.pop();
    }
    return find;
}

二叉樹中兩個節(jié)點最近的公共父節(jié)點

首先需要明白，根節(jié)點肯定是二叉樹中任意兩個節(jié)點的公共父節(jié)點（不一定是最近的）盖腕，因此二叉樹中2個節(jié)點的最近公共父節(jié)點一定在從根節(jié)點到這個節(jié)點的路徑上赫冬。因此我們可以先分別找到從根節(jié)點到這2個節(jié)點的路徑，再從這兩個路徑中找到最近的公共父節(jié)點溃列。

/**
 * 二叉樹種兩個節(jié)點的最近公共節(jié)點
 * @param rootNode 根節(jié)點
 * @param nodeA 第一個節(jié)點
 * @param nodeB 第二個節(jié)點
 * @return 最近的公共節(jié)點
 */
public static int parentOfNode(BinaryTreeNode<Integer> rootNode, int nodeA, int nodeB) {
    if (rootNode == null) {
        return -1;
    }
    //兩個節(jié)點是同一個節(jié)點
    if (nodeA == nodeB) {
        return nodeA;
    }
    //其中一個點為根節(jié)點
    if (rootNode.value == nodeA || rootNode.value == nodeB) {
        return rootNode.value;
    }
    //從根節(jié)點到節(jié)點A的路徑
    Stack<BinaryTreeNode> pathA = pathOfTreeNode(rootNode, nodeA);
    //從根節(jié)點到節(jié)點B的路徑
    Stack<BinaryTreeNode> pathB = pathOfTreeNode(rootNode, nodeB);
    //尋找的節(jié)點不在樹中
    if (pathA.size() == 0 || pathB.size() == 0) {
        return -1;
    }
    //將路徑的數(shù)據(jù)結(jié)構(gòu)劲厌，變?yōu)閿?shù)組
    int[] arrayA = new int[pathA.size()];
    int[] arrayB = new int[pathB.size()];
    for (int i = pathA.size() - 1; i >= 0; i--){
        arrayA[i] = (int) pathA.pop().value;
    }
    for (int i = pathB.size() - 1; i >= 0; i--) {
        arrayB[i] = (int) pathB.pop().value;
    }
    //第i+1個不相同的節(jié)點出現(xiàn)，則第i個節(jié)點為最近公共節(jié)點
    for (int i = 0; i < arrayA.length - 1 && i < arrayB.length - 1; i++) {
        if (arrayA[i + 1] != arrayB[i + 1]) {
            return arrayA[i];
        }
        if (i + 1 == arrayA.length - 1) {
            return arrayA[arrayA.length - 1];
        }
        if (i + 1 == arrayB.length - 1) {
            return arrayB[arrayB.length - 1];

        }
    }
    return -1;
}

二叉樹中兩個節(jié)點之間的路徑

從查找最近公共父節(jié)點衍生出來的听隐。

/**
 * 二叉樹中兩個節(jié)點之間的路徑
 * @param rootNode 根節(jié)點
 * @param nodeA 第一個節(jié)點
 * @param nodeB 第二個節(jié)點
 * @return 路徑
 */
public static List<Integer> pathFromNode(BinaryTreeNode<Integer> rootNode, int nodeA, int nodeB) {
    if (rootNode == null) {
        return null;
    }
    List<Integer> result = new ArrayList<>();
    if (nodeA == nodeB) {
        result.add(nodeA);
        result.add(nodeB);
        return result;
    }
    //從根節(jié)點到節(jié)點A的路徑
    Stack<BinaryTreeNode> pathA = pathOfTreeNode(rootNode, nodeA);
    //從根節(jié)點到節(jié)點B的路徑
    Stack<BinaryTreeNode> pathB = pathOfTreeNode(rootNode, nodeB);
    if (rootNode.value == nodeB) {
        pathA.forEach(new Consumer<BinaryTreeNode>() {
            @Override
            public void accept(BinaryTreeNode binaryTreeNode) {
                result.add((Integer) binaryTreeNode.value);
            }
        });
        return result;
    }
    if (rootNode.value == nodeA) {
        pathB.forEach(new Consumer<BinaryTreeNode>() {
            @Override
            public void accept(BinaryTreeNode binaryTreeNode) {
                result.add((Integer) binaryTreeNode.value);
            }
        });
        return result;
    }
    //尋找的節(jié)點不在樹中
    if (pathA.size() == 0 || pathB.size() == 0) {
        return null;
    }
    //將路徑的數(shù)據(jù)結(jié)構(gòu)补鼻，變?yōu)閿?shù)組
    int[] arrayA = new int[pathA.size()];
    int[] arrayB = new int[pathB.size()];
    for (int i = pathA.size() - 1; i >= 0; i--){
        arrayA[i] = (int) pathA.pop().value;
    }
    for (int i = pathB.size() - 1; i >= 0; i--) {
        arrayB[i] = (int) pathB.pop().value;
    }
    //第i+1個不相同的節(jié)點出現(xiàn)，則第i個節(jié)點為最近公共節(jié)點
    int lastNode = -1;
    for (int i = 0; i < arrayA.length - 1 && i < arrayB.length - 1; i++) {
        if (arrayA[i + 1] != arrayB[i + 1]) {
            lastNode = i;
            break;
        }
        if (i + 1 == arrayA.length - 1) {
            lastNode = arrayA.length - 1;
            break;
        }
        if (i + 1 == arrayB.length - 1) {
            lastNode = arrayB.length - 1;
            break;
        }
    }
    for (int i = arrayA.length - 1; i >= lastNode; i--) {
        result.add(arrayA[i]);
    }
    for (int i = lastNode + 1; i < arrayB.length; i++) {
        result.add(arrayB[i]);
    }
    return result;
}

翻轉(zhuǎn)二叉樹

翻轉(zhuǎn)二叉樹，又叫求二叉樹的鏡像风范，就是把二叉樹的左右子樹對調(diào)（當然是遞歸的）

/**
 * 翻轉(zhuǎn)二叉樹
 * @param rootNode 根節(jié)點
 * @return 翻轉(zhuǎn)后的二叉樹
 */
public static BinaryTreeNode invertBinaryTree(BinaryTreeNode<Integer> rootNode) {
    if (rootNode == null) {
        return null;
    }
    //只有一個根節(jié)點
    if (rootNode.leftNode == null && rootNode.rightNode == null) {
        return rootNode;
    }
    invertBinaryTree(rootNode.leftNode);
    invertBinaryTree(rootNode.rightNode);
    BinaryTreeNode tempNode = rootNode.leftNode;
    rootNode.leftNode = rootNode.rightNode;
    rootNode.rightNode = tempNode;
    return rootNode;
}

完全二叉樹

A Complete Binary Tree （CBT) is a binary tree in which every level, 
except possibly the last, is completely filled, and all nodes 
are as far left as possible.

換句話說咨跌，完全二叉樹從根結(jié)點到倒數(shù)第二層滿足完美二叉樹，最后一層可以不完全填充硼婿，其葉子結(jié)點都靠左對齊锌半。

例如：

完全二叉樹

根據(jù)《李春葆數(shù)據(jù)結(jié)構(gòu)教程》書上的完全二叉樹定義為：“二叉樹中最多只有最下面兩層節(jié)點的度數(shù)小于二，并且最下邊的一層的葉子節(jié)點都一次排列在該層最左邊的位置上寇漫，這樣的二叉樹稱為完全二叉樹”刊殉。

特點

• 葉子節(jié)點只可能在層次最大的兩層出現(xiàn)；
• 對于最大層次中的葉子節(jié)點州胳，都一次排列在該層的最左邊的位置上冗澈；
• 如果有度為一的葉子節(jié)點，只可能有一個陋葡，且該節(jié)點只有左孩子而無有孩子亚亲。

采用優(yōu)先廣度遍歷的算法，從上到下腐缤，從左到右依次入隊列捌归。我們可以設(shè)置一個標志位flag，當子樹滿足完全二叉樹時岭粤，設(shè)置flag=true惜索。當flag=ture而節(jié)點又破壞了完全二叉樹的條件，那么它就不是完全二叉樹剃浇。

/**
 * 是否完全二叉樹
 * 完全二叉樹：若設(shè)二叉樹的高度為h巾兆，除第h層外，其它各層的結(jié)點數(shù)都達到最大個數(shù)虎囚，第h層有葉子結(jié)點角塑，并且葉子結(jié)點都是從左到右依次排布
 * @param rootNode 根節(jié)點
 * @return 是否是完全二叉樹
 */
public static boolean isCompleteBinaryTree(BinaryTreeNode<Integer> rootNode) {
    if (rootNode == null) {
        return false;
    }
    //左子樹和右子樹都是空，則是完全二叉樹
    if (rootNode.leftNode == null && rootNode.rightNode == null) {
        return true;
    }
    //左子樹是空淘讥，右子樹不是空圃伶，則不是完全二叉樹
    if (rootNode.leftNode == null && rootNode.rightNode != null) {
        return false;
    }
    Deque<BinaryTreeNode<Integer>> queue = new LinkedList<>();
    queue.add(rootNode);
    //是否滿足二叉樹
    boolean isComplete = false;
    while (queue.size() > 0) {
        BinaryTreeNode<Integer> node = queue.pop();
        //左子樹為空且右子樹不為空，則不是完全二叉樹
        if (node.leftNode == null && node.rightNode != null) {
            return false;
        }
        //前面的節(jié)點已滿足完全二叉樹,如果還有孩子節(jié)點蒲列，則不是完全二叉樹
        if (isComplete && (node.leftNode != null || node.rightNode != null)) {
            return false;
        }
        //右子樹為空窒朋，則已經(jīng)滿足完全二叉樹
        if (node.rightNode == null) {
            isComplete = true;
        }
        //將子節(jié)點壓入
        if (node.leftNode != null) {
            queue.add(node.leftNode);
        }
        if (node.rightNode != null) {
            queue.add(node.rightNode);
        }
    }
    return isComplete;
}

判斷二叉樹是否滿二叉樹

滿二叉樹定義為：除了葉結(jié)點外每一個結(jié)點都有左右子葉且葉子結(jié)點都處在最底層的二叉樹

滿二叉樹的一個特性是：葉子數(shù)=2^(深度-1)，因此我們可以根據(jù)這個特性來判斷二叉樹是否是滿二叉樹蝗岖。

/**
 * 是否滿二叉樹
 * 滿二叉樹：除了葉結(jié)點外每一個結(jié)點都有左右子葉且葉子結(jié)點都處在最底層的二叉樹
 * @param rootNode 根節(jié)點
 * @return 是否滿二叉樹
 */
public static boolean isFullBinaryTree(BinaryTreeNode<Integer> rootNode) {
    if (rootNode == null) {
        return false;
    }
    int depth = depthOfTree(rootNode);
    int leafNum = numberOfLeafsInTree(rootNode);
    if (leafNum == Math.pow(2, (depth - 1))) {
        return true;
    }
    return false;
}

平衡二叉樹

平衡二叉樹定義為：它是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過1侥猩，并且左右兩個子樹都是一棵平衡二叉樹。平衡二叉樹又叫AVL樹抵赢。

/**
 * 是否平衡二叉樹
 * @param rootNode 根節(jié)點
 * @return 是否平衡二叉樹
 */
static int height;
public static boolean isAVLBinaryTree(BinaryTreeNode<Integer> rootNode) {
    if (rootNode == null) {
        height = 0;
        return true;
    }
    if (rootNode.leftNode == null && rootNode.rightNode == null) {
        height = 1;
        return true;
    }
    boolean isAVLLeft = isAVLBinaryTree(rootNode.leftNode);
    int heightLeft = height;
    boolean isAVLRight = isAVLBinaryTree(rootNode.rightNode);
    int heightRight = height;
    height = Math.max(heightLeft, heightRight) + 1;
    return isAVLLeft && isAVLRight && Math.abs(heightLeft - heightRight) <= 1;
}

本來是想看紅黑樹的欺劳，但關(guān)于樹相關(guān)的知識忘記的差不多了洛退，這幾天抽時間看了看二叉樹的相關(guān)知識，作為筆記整理杰标。
--->>>>>>>>代碼
參考文章：
二叉樹-你必須要懂１印（二叉樹相關(guān)算法實現(xiàn)-iOS）

文章到這里就全部講述完啦，若有其他需要交流的可以留言哦~腔剂！~媒区！