使用迭代實(shí)現(xiàn)了先,中,后序遍歷二叉樹(shù).時(shí)間復(fù)雜度均為O(n);
前序遍歷
沒(méi)什么好說(shuō)的,棧中取當(dāng)前節(jié)點(diǎn),先壓右節(jié)點(diǎn),后壓左節(jié)點(diǎn).然后取當(dāng)前節(jié)點(diǎn)值,取值操作任意位置即可,因?yàn)閷?xiě)成這樣必然取當(dāng)前節(jié)點(diǎn)是先序的.
public static List<Object> preTraversal(BTree bTree) {
if (bTree == null) {
return null;
}
List<Object> results = new ArrayList();
List<BTree> stack = new ArrayList();
BTree cur = bTree;
int len = 0;
stack.add(cur);
while((len = stack.size()) > 0) {
cur = stack.remove(len - 1);
if (cur != null) {
stack.add(cur.right);
stack.add(cur.left);
results.add(cur.value);
}
}
return results;
}
中序遍歷
看到了網(wǎng)上有這樣實(shí)現(xiàn)中序遍歷的代碼,兩層while循環(huán)是沒(méi)有必要的.
不推薦: 時(shí)間復(fù)雜度O(n^2)
public static List<Integer> inorderTraversal(TreeNode root) {
if (root == null) {
return null;
}
List<Integer> list = new ArrayList<Integer>();
Stack<TreeNode> s = new Stack<TreeNode>();
do {
while (root != null) {
s.push(root);
root = root.left;
}
if (!s.isEmpty()) {
TreeNode node = s.pop();
list.add(node.val);
root = node.right;
}
} while (!s.isEmpty() || root != null);
return list;
}
思考中序的規(guī)則:
首先遍歷左子樹(shù)都弹，然后訪問(wèn)根結(jié)點(diǎn)墨闲，最后遍歷右子樹(shù)
?也就是說(shuō)我們有一個(gè)節(jié)點(diǎn),優(yōu)先會(huì)去訪問(wèn)其左節(jié)點(diǎn),這就隱藏了一個(gè)信息(為了保證之后輸出根節(jié)點(diǎn),根節(jié)點(diǎn)需要入棧).
?同時(shí)我們要意識(shí)到,葉子節(jié)點(diǎn)也是根節(jié)點(diǎn),不過(guò)其左右子樹(shù)都為空.遍歷整棵樹(shù),我們只需要輸出根節(jié)點(diǎn)就可以做到.
什么時(shí)候可以輸出根節(jié)點(diǎn)呢?
?當(dāng)然是遍歷到的當(dāng)前節(jié)點(diǎn)為空的時(shí)候(說(shuō)明要么是棧頂元素的左子樹(shù)為空,要么是棧頂元素的左子樹(shù)已經(jīng)遍歷完成).我們從棧頂取出一個(gè)根節(jié)點(diǎn)輸出.同時(shí),繼續(xù)遍歷其右子樹(shù).
推薦: 時(shí)間復(fù)雜度O(n)
public static List<Object> inOrderTraversal(BTree bTree) {
if (bTree == null) {
return null;
}
List<Object> results = new ArrayList();
List<BTree> stack = new ArrayList();
BTree cur = bTree;
int len = 0;
while(cur != null || (len = stack.size()) > 0) {
if (cur != null) {
stack.add(cur);
cur = cur.left;
} else {
cur = stack.remove(len - 1);
results.add(cur.value);
cur = cur.right;
}
}
return results;
}
后序遍歷
思考后序遍歷的規(guī)則
首先遍歷左子樹(shù)卵渴，然后遍歷右子樹(shù)柱锹，最后訪問(wèn)根結(jié)點(diǎn)。
我們可以通過(guò)標(biāo)記上一次訪問(wèn)的節(jié)點(diǎn),來(lái)判斷是否訪問(wèn)過(guò)該節(jié)點(diǎn)的左右子樹(shù)
public static List<Object> postOrderTraversal(BTree bTree) {
if (bTree == null) {
return null;
}
List<Object> results = new ArrayList<>();
List<BTree> stack = new ArrayList<>();
int len = 0;
BTree cur = bTree;
BTree last = null;
stack.add(cur);
while((len = stack.size()) > 0) {
cur = stack.get(len - 1);
boolean isLeaf = cur.left == null && cur.right == null;
boolean isVisited = (cur.right == null && cur.left == last) || cur.right == last;
if (isLeaf || isVisited) {
stack.remove(len - 1);
results.add(cur.value);
last = cur;
} else {
if (cur.right != null) {
stack.add(cur.right);
}
if (cur.left != null) {
stack.add(cur.left);
}
}
}
return results;
}
層次遍歷
這個(gè)也沒(méi)啥好說(shuō)的,通過(guò)隊(duì)列先進(jìn)先出的特性進(jìn)行廣度遍歷, 注意先出隊(duì)
public static List<Object> levelTraversal(BTree bTree) {
if (bTree == null) {
return null;
}
List<BTree> queue = new LinkedList<>();
List<Object> results = new ArrayList<>();
BTree cur = bTree;
int len = 0;
queue.add(cur);
while((len = queue.size()) > 0) {
cur = queue.remove(0);
if (cur.left != null) {
queue.add(cur.left);
}
if (cur.right != null) {
queue.add(cur.right);
}
results.add(cur.value);
}
return results;
}
