基本概念
- 根 (root)
- 叶子节点 (leaf)
- 子节点 (child)
- 节点的度 (degree)
- 树的高度 (height)
- 二叉树
完全二叉树
满二叉树 - 二叉树的性质
- 二叉搜索树 (BST)
设计与实现
- 节点
class TreeNode {
int val;
TreeNode left, right;
TreeNode (int val) {
this.val = val;
this.left = null;
this.right = null;
}
}
- 二叉树遍历
先序遍历
// version 1 : recursion
public class Solution {
List<Integer> res;
/**
* @param root: A Tree
* @return: Preorder in ArrayList which contains node values.
*/
public List<Integer> preorderTraversal(TreeNode root) {
res = new ArrayList<>();
helper(root);
return res;
}
private void helper(TreeNode root) {
if (root == null) {
return;
}
res.add(root.val);
helper(root.left);
helper(root.right);
}
}
// version 2 : non - recursion (important!)
public class Solution {
/**
* @param root: A Tree
* @return: Preorder in ArrayList which contains node values.
*/
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
if (root == null) {
return res;
}
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode cur = stack.pop();
res.add(cur.val);
if (cur.right != null) {
stack.push(cur.right);
}
if (cur.left != null) {
stack.push(cur.left);
}
}
return res;
}
}
中序遍历
// version 1 : recursion
public class Solution {
List<Integer> res;
/**
* @param root: A Tree
* @return: Inorder in ArrayList which contains node values.
*/
public List<Integer> inorderTraversal(TreeNode root) {
res = new ArrayList<>();
helper(root);
return res;
}
private void helper(TreeNode root) {
if (root == null) {
return;
}
helper(root.left);
res.add(root.val);
helper(root.right);
}
}
// version 2 : non - recursion (important!)
public class Solution {
/**
* @param root: A Tree
* @return: Inorder in ArrayList which contains node values.
*/
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
while (root != null) {
stack.push(root);
root = root.left;
}
while (!stack.isEmpty()) {
TreeNode cur = stack.pop();
res.add(cur.val);
if (cur.right != null) {
cur = cur.right;
while (cur != null) {
stack.push(cur);
cur = cur.left;
}
}
}
return res;
}
}
后序遍历
// version 1 : recursion (by divide and conquer)
public class Solution {
/**
* @param root: A Tree
* @return: Postorder in ArrayList which contains node values.
*/
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
if (root == null) {
return res;
}
res.addAll(postorderTraversal(root.left));
res.addAll(postorderTraversal(root.right));
res.add(root.val);
return res;
}
}
// version 2 : non - recursion (important!)
public class Solution {
/**
* @param root: A Tree
* @return: Postorder in ArrayList which contains node values.
*/
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
if (root == null) {
return res;
}
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode cur = stack.pop();
res.add(cur.val);
if (cur.left != null) {
stack.push(cur.left);
}
if (cur.right != null) {
stack.push(cur.right);
}
}
Collections.reverse(res);
return res;
}
}
// from: https://github.com/mission-peace/interview/blob/master/src/com/interview/tree/MorrisTraversal.java
public class MorrisTraversal {
public void inorder(Node root) {
Node current = root;
while(current != null) {
//left is null then print the node and go to right
if (current.left == null) {
System.out.print(current.data + " ");
current = current.right;
}
else {
//find the predecessor.
Node predecessor = current.left;
//To find predecessor keep going right till right node is not null or right node is not current.
while(predecessor.right != current && predecessor.right != null){
predecessor = predecessor.right;
}
//if right node is null then go left after establishing link from predecessor to current.
if(predecessor.right == null){
predecessor.right = current;
current = current.left;
}else{ //left is already visit. Go rigth after visiting current.
predecessor.right = null;
System.out.print(current.data + " ");
current = current.right;
}
}
}
}
public void preorder(Node root) {
Node current = root;
while (current != null) {
if(current.left == null) {
System.out.print(current.data + " ");
current = current.right;
}
else {
Node predecessor = current.left;
while(predecessor.right != current && predecessor.right != null) {
predecessor = predecessor.right;
}
if(predecessor.right == null){
predecessor.right = current;
System.out.print(current.data + " ");
current = current.left;
}else{
predecessor.right = null;
current = current.right;
}
}
}
}
}
Java中Balanced BST的实现
- TreeSet
元素按照某种顺序被排序。
基于HashMap实现，无容量限制。
不允许元素重复。
查找与删除的时间复杂度为。
Set<Integer> s = new TreeSet<>();
- TreeMap
基于红黑树实现，无容量限制。
