04-二分搜索树

二分搜索树

二分搜索算法

递归方式

JavaScript版

var search = function(nums, target) {
  return binarySearch(nums, target, 0, nums.length - 1);
};
var binarySearch = function(nums, target, left, right) {
  if (left > right) {
    return -1;
  }
  let middle = Math.trunc((left + right) / 2);
  if (nums[middle] < target) {
    return binarySearch(nums, target, middle + 1, right);
  } else if (nums[middle] > target) {
    return binarySearch(nums, target, left, middle -1);
  } else {
    return middle;
  }
};

Java版

class Solution {
  public int search(int[] nums, int target) {
    return binarySearch(nums, target, 0, nums.length - 1);
  }
  public int binarySearch(int[] nums, int target, int left, int right) {
    if (left > right) {
      return -1;
    }
    int middle = (left + right) / 2;
    if (nums[middle] < target) {
      return binarySearch(nums, target, middle + 1, right);
    } else if (nums[middle] > target) {
      return binarySearch(nums, target, left, middle - 1);
    } else {
      return middle;
    }
  }
}

非递归方式

JavaScript版

var search = function(nums, target) {
  let left = 0;
  let right = nums.length - 1;
  while (left <= right) {
    let middle = Math.trunc((left + right) / 2);
    if (nums[middle] < target) {
      left = middle + 1;
    } else if (nums[middle] > target) {
      right = middle - 1;
    } else {
      return middle;
    }
  }
  return -1;
};

Java版

class Solution {
  public int search(int[] nums, int target) {
		int left = 0;
    int right = nums.length - 1;
    while (left <= right) {
      int middle = (left + right) / 2;
      if (nums[middle] < target) {
        left = middle + 1;
      } else if (nums[middle] > target) {
        right = middle - 1;
      } else {
        return middle;
      }
    }
    return -1;
  }
}

深度优先遍历

JavaScript版

class TreeNode {
  constructor (value, left, right) {
    this.value = value;
    this.left = left;
    this.right = right;
  }
}
var preorderTraversal = function(root) {
  const result = new Array();
  if (root == null) {
    return result;
  }
  const stack = new Array();
  let curr = root;
  while (curr != null || stack.length > 0) {
    while (curr != null) {
      result.push(curr.val);
      stack.push(curr);
      curr = curr.left;
    }
    curr = stack.pop();
    curr = curr.right;
  }
  return result;
};
var inorderTraversal = function(root) {
  const result = new Array();
  if (root == null) {
    return result;
  }
  const stack = new Array();
  let curr = root;
  while (curr != null || stack.length > 0) {
    while (curr != null) {
      stack.push(curr);
      curr = curr.left;
    }
    curr = stack.pop();
    result.push(curr.value);
    curr = curr.right;
  }
  return result;
};
var postorderTraversal = function(root) {
  const result = new Array();
  if (root == null) {
    return result;
  }
  const stack = new Array();
  let prev = null;
  let curr = root;
  while (curr !=null || stack.length > 0) {
    while (curr != null) {
      stack.push(curr);
      curr = curr.left;
    }
    curr = stack.pop();
    if (curr.right == null || curr.right == prev) {
      result.push(curr.value);
      prev = curr;
      curr = null;
    } else {
      stack.push(curr);
      curr = curr.right;
    }
  }
  return result;
};

Java版

class Solution {
  private class TreeNode {
    int value;
    TreeNode left;
    TreeNode right;
    TreeNode(int value, TreeNode left, TreeNode right) {
      this.value = value;
      this.left = left;
      this.right = right;
    }
	}
  public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null) {
      return result;
    }
    Deque<TreeNode> stack = new LinkedList<>();
    TreeNode curr = root;
    while (curr != null || !stack.isEmpty()) {
      while (curr != null) {
        result.add(curr.value);
        stack.push(curr);
        curr = curr.left;
      }
      curr = stack.pop();
      curr = curr.right;
    }
    return result;
  }
  public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null) {
      return result;
    }
    Deque<TreeNode> stack = new LinkedList<>();
    TreeNode curr = root;
    while (curr != null || !stack.isEmpty()) {
      while (curr != null) {
        stack.push(curr);
        curr = curr.left;
      }
      curr = stack.pop();
      result.add(curr.value);
      curr = curr.right;
    }
    return result;
  }
  public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null) {
      return result;
    }
    Deque<TreeNode> stack = new LinkedList<>();
    TreeNode curr = root;
    TreeNode prev = null;
    while (curr != null || !stack.isEmpty()) {
      while (curr != null) {
        stack.push(curr);
        curr = curr.left;
      }
      curr = stack.pop();
      if (curr.right == null || curr.right == prev) {
        result.add(curr.value);
        prev = curr;
        curr = null;
      } else {
        stack.push(curr);
        curr = curr.right;
      }
    }
    return result;
  }
  private class Command {
    TreeNode node;
    Boolean bingo;
    static Boolean GO = false;
    static Boolean TO = true;
    public Command(TreeNode node, Boolean bingo) {
      this.node = node;
      this.bingo = bingo;
    }
  }
  public static ArrayList<Integer> order(TreeNode root) {
    ArrayList<Integer> result = new ArrayList<>();
    if (root == null) {
      return result;
    }
    Deque<Command> stack = new LinkedList<>();
    stack.push(new Command(root, Command.GO));
    while (!stack.isEmpty()) {
      Command command = stack.pop();
      if (command.bingo == Command.TO) {
        result.add(command.node.val);
      } else {
        // stack.push(new Command(command.node, Command.TO));  //后续
        if (command.node.right != null) {
          stack.push(new Command(command.node.right, Command.GO));
        }
        // stack.push(new Command(command.node, Command.TO));  //中序
        if (command.node.left != null) {
          stack.push(new Command(command.node.left, Command.GO));
        }
        stack.push(new Command(command.node, Command.TO));  //前序
      }
    }
    return result;
  }
}

广度优先遍历

JavaScript版

class TreeNode {
  constructor (value, left, right) {
    this.value = value;
    this.left = left;
    this.right = right;
  }
}
var levelOrder = function(root) {
	const result = new Array();
  if (root == null) {
    return result;
  }
  const deque = new Array();
  deque.push(root);
  while (deque.length > 0) {
    const level = new Array();
    const currLevelSize = deque.length;
    for (let i = 0; i < currLevelSize; i++) {
      let node = deque.shift();
      level.push(node.value);
      if (node.left != null) {
        deque.push(node.left);
      }
      if (node.right != null) {
        deque.push(node.right);
      }
    }
    result.push(level);
  }
  return result;
};

Java版

class Solution {
  private class TreeNode {
    int value;
    TreeNode left;
    TreeNode right;
    TreeNode(int value, TreeNode left, TreeNode right) {
      this.value = value;
      this.left = left;
      this.right = right;
    }
	}
  public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    if (root == null) {
      return result;
    }
    Deque<TreeNode> queue = new LinkedList<>();
    queue.addLast(root);
    while (!queue.isEmpty()) {
      List<Integer> level = new ArrayList<>();
      int currentLevelSize  = queue.size();
      for (int i = 0; i < currentLevelSize; i++) {
        TreeNode node = queue.removeFirst();
        level.add(node.value);
        if (node.left != null) {
          queue.addLast(node.left);
        }
        if (node.right != null) {
          queue.addLast(node.right);
        }
      }
      result.add(level);
    }
    return result;
  }
}