Algorithm - mpgcompile/principle GitHub Wiki

一: 二叉树深度

public int treeDepth(TreeNode treeNode) {
    if (treeNode == null) return 0;

    int left = treeDepth(treeNode.left());
    int right = treeDepth(treeNode.right());

    return Math.max(left, right);
}

二: 二叉树前、中、后序

// 前序 根结点 ---> 左子树 ---> 右子树 // 中序 左子树 ---> 根结点 ---> 右子树 // 前序 左子树 ---> 右子树 ---> 根结点 // 层次遍历 1 2 3 4 5 6 7 8

public void beforeSort(TreeNode root) {

    if (root != null) {

        System.out.print("root = [" + root.val + "]");
        beforeSort(root.left);
        beforeSort(root.right);
    }
}

//非递归
public void beforeSort2(TreeNode root) {

    LinkedList<TreeNode> stack = new LinkedList<>();

    TreeNode nodeT = root;

    while (nodeT != null || !stack.isEmpty()) {

        if (nodeT != null){
            System.out.print(nodeT.val+"  ");
            stack.push(nodeT);
            nodeT = nodeT.left;
        }else {
            TreeNode node  = stack.poll();
            nodeT = node.right;
        }
    }
}

三: 链表环形

public boolean isCycle(LinkedNode root) {

    if (root == null || root.next() == null) return false;


    LinkedNode slow = root;
    LinkedNode fast = root.next();

    while (fast != null) {

        if (slow == fast) return true;

        slow = slow.next();
        fast = fast.next().next();

    }

    return false;
}

四: 链表反转

public LinkedNode reverseList(LinkedNode root) {

    LinkedNode prev = null;
    LinkedNode curr = root;

    while (curr != null) {
        LinkedNode next = curr.next();
        curr.next() = prev;
        prev = curr;
        curr = next;
    }

    return prev;
}

public LinkedNode reverseList1(LinkedNode root){
    if (root == null || root.next() == null){
        return root;
    }

    LinkedNode curr = reverseList1(root.next());
    root.next().next() = root;
    root.next() = null;
    return curr;
}

五: 排序

六: 二分查找

public static int search(int[] attr, int target) {
    int pivot, left = 0, right = attr.length - 1;

    while (left <= right) {
        pivot = left + (right - left) / 2;
        if (attr[pivot] < target) {
            left = pivot + 1;
        } else {
            right = pivot - 1;
        }

        return pivot;
    }

    return -1;
}

七: 利用栈实现队列

private Stack<Integer> s1 = new Stack<>();
private Stack<Integer> s2 = new Stack<>();

int front;

// Push element x to the back of queue.
public void push(int x) {
    if (s1.empty())
        front = x;
    s1.push(x);
}


// Removes the element from in front of queue.
public void pop() {
    if (s2.isEmpty()) {
        while (!s1.isEmpty())
            s2.push(s1.pop());
    }
    s2.pop();
}

八：最长子数组求和

public int maxArray(int[] nums){

 int res = nums[0];

 for(int i = 1; i < nums.length; i++) {
     nums[i] += Math.max(nums[i - 1], 0);
     res = Math.max(res, nums[i]);
 }

 return res;

}

⚠️ **GitHub.com Fallback** ⚠️