- 二叉樹基本概念
二叉樹是每個(gè)結(jié)點(diǎn)至多有兩顆子樹的樹颊郎，子樹有左右之分憋飞，其次序不能任意顛倒。 - 幾種特殊二叉樹
1） 滿二叉樹：高度為h姆吭，并且含有2h-1個(gè)結(jié)點(diǎn)的二叉樹榛做。即樹的每一層都是滿的（每層結(jié)點(diǎn)數(shù)為2(h-1)） 。若對(duì)滿二叉樹編號(hào)，從上自下检眯，從左至右厘擂，根節(jié)點(diǎn)編號(hào)為1，則對(duì)于編號(hào)為i 的結(jié)點(diǎn)锰瘸，如果有雙親刽严，則雙親為?i/2?，如果有左孩子避凝，左孩子為2i舞萄，如果有右孩子，右孩子為2i+1.如下圖所示：
滿二叉樹.png
2） 完全二叉樹：若1個(gè)高度為h管削，含有n個(gè)結(jié)點(diǎn)的二叉樹倒脓，按照從上自下，從左至右的順序?qū)Y(jié)點(diǎn)進(jìn)行編號(hào)含思，1~n的結(jié)點(diǎn)與滿二叉樹一一對(duì)應(yīng)崎弃，則該二叉樹為完全二叉樹。如下圖所示：
完全二叉樹.png
3） 二叉排序樹：左子樹上所有關(guān)鍵字均小于根節(jié)點(diǎn)關(guān)鍵字含潘，右子樹所有結(jié)點(diǎn)關(guān)鍵字均大于根節(jié)點(diǎn)關(guān)鍵字饲做。左子樹和右子樹又各是一顆二叉排序樹。
4） 平衡二叉樹：樹上任一結(jié)點(diǎn)的左子樹和右子樹的深度之差不超過1遏弱。 - 二叉樹遍歷
二叉樹定義
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
非遞歸實(shí)現(xiàn)借助棧盆均，前序、中序腾窝、后序是相對(duì)于根節(jié)點(diǎn)而言缀踪，根據(jù)根節(jié)點(diǎn)輸出的位置居砖，根虹脯、左、右為前序遍歷奏候；左循集、根、右為中序遍歷蔗草；左咒彤、右、根為后序遍歷咒精。
1） 前序遍歷(PreOrder)：
如果二叉樹為空镶柱，則什么也不做；否則：
a)訪問根節(jié)點(diǎn)模叙；
b)先序遍歷左子樹歇拆；
c)先序遍歷右子樹。
遞歸實(shí)現(xiàn)：
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
if(root == null)
return list;
helper(root, list);
return list;
}
public void helper(TreeNode root, List<Integer> list) {
list.add(root.val);
if(root.left != null)
helper(root.left, list);
if(root.right != null)
helper(root.right, list);
}
常規(guī)版非遞歸實(shí)現(xiàn)：先將根節(jié)點(diǎn)入棧，然后彈出（訪問根節(jié)點(diǎn)）故觅，然后將其右結(jié)點(diǎn)入棧厂庇，再將其左結(jié)點(diǎn)入棧（棧是先進(jìn)后出，我們需要先訪問左結(jié)點(diǎn)输吏，所以先將右結(jié)點(diǎn)入棧）权旷，然后彈出左結(jié)點(diǎn)，對(duì)左結(jié)點(diǎn)也進(jìn)行同樣的操作（右結(jié)點(diǎn)先入棧贯溅，左結(jié)點(diǎn)入棧）拄氯，直至棧為空并且訪問完了所有結(jié)點(diǎn)。
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
if(root == null)
return list;
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while(!stack.isEmpty()) {
root = stack.pop();
list.add(root.val);
if(root.right != null)
stack.push(root.right);
if(root.left != null)
stack.push(root.left);
}
return list;
}
簡單版非遞歸實(shí)現(xiàn)：與上一種方式的不同是在訪問根節(jié)點(diǎn)的時(shí)機(jī)不相同它浅。常規(guī)方式是在出棧時(shí)訪問根節(jié)點(diǎn)坤邪，將其寫入list中，而簡單方式是入棧的同時(shí)將值寫入list罚缕，所以我們只要保證按照前序遍歷的順序去遍歷二叉樹即可艇纺。
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
Deque<TreeNode> stack = new ArrayDeque<>();
TreeNode node = root;
while(node != null || !stack.isEmpty()) {
if(node != null) {
stack.push(node);
list.add(node.val);
node = node.left;
}else {
node = stack.pop();
node = node.right;
}
}
return list;
}
2） 中序遍歷(InOrder)：
如果二叉樹為空，則什么也不做邮弹；否則：
a)中序遍歷左子樹黔衡；
b)訪問根節(jié)點(diǎn)；
c)中序遍歷右子樹腌乡。
遞歸實(shí)現(xiàn)：
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
if(root == null)
return list;
helper(root, list);
return list;
}
public void helper(TreeNode root, List<Integer> list) {
if(root.left != null)
helper(root.left, list);
list.add(root.val);
if(root.right != null)
helper(root.right, list);
}
常規(guī)版非遞歸實(shí)現(xiàn)：從根節(jié)點(diǎn)依次遍歷左結(jié)點(diǎn)盟劫，如果左結(jié)點(diǎn)沒有被訪問過，則入棧与纽，當(dāng)沒有左結(jié)點(diǎn)或左結(jié)點(diǎn)被訪問過的時(shí)候侣签，彈出棧頂元素，將其寫入list急迂，并將其右結(jié)點(diǎn)入棧影所。重復(fù)上述操作。
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
Map<TreeNode, Integer> map = new HashMap<>();
Stack<TreeNode> stack = new Stack<>();
if(root == null)
return list;
stack.push(root);
while(!stack.isEmpty()) {
root = stack.peek();
while(root.left != null) {
if(map.containsKey(root.left))
break;
stack.push(root.left);
root = root.left;
}
root = stack.pop();
list.add(root.val);
map.put(root, 1);
if(root.right != null)
stack.push(root.right);
}
return list;
}
簡單版非遞歸實(shí)現(xiàn):從根節(jié)點(diǎn)依次將左結(jié)點(diǎn)入棧僚碎，當(dāng)沒有左結(jié)點(diǎn)的時(shí)候猴娩，彈出棧頂元素，將其寫入list勺阐，并將其右結(jié)點(diǎn)入棧卷中。重復(fù)上述操作。與常規(guī)方法相比渊抽，省去了查看左子樹是否被訪問過的步驟蟆豫，對(duì)每個(gè)結(jié)點(diǎn)，都是先遍歷其左子樹懒闷，所以當(dāng)訪問到該結(jié)點(diǎn)的時(shí)候十减，可以確保其左子樹已經(jīng)被訪問過了徙瓶，只需要訪問其本身和其右結(jié)點(diǎn)即可。
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
Deque<TreeNode> stack = new ArrayDeque<>();
TreeNode node = root;
while(node!=null || !stack.isEmpty()) {
if(node != null) {
stack.push(node);
node = node.left;
}else {
node = stack.pop();
list.add(node.val);
node = node.right;
}
}
return list;
}
3） 后序遍歷(PostOrder)：
如果二叉樹為空嫉称，則什么也不做侦镇；否則：
a)后序遍歷左子樹；
b)后序遍歷右子樹织阅；
c)訪問根節(jié)點(diǎn)壳繁。
遞歸實(shí)現(xiàn)：
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
if(root == null)
return list;
helper(root, list);
return list;
}
public void helper(TreeNode root, List<Integer> list) {
if(root.left != null)
helper(root.left, list);
if(root.right != null)
helper(root.right, list);
list.add(root.val);
}
常規(guī)版非遞歸實(shí)現(xiàn)：將根節(jié)點(diǎn)左子樹入棧，當(dāng)訪問到葉子結(jié)點(diǎn)荔棉，出棧闹炉，查看該葉子結(jié)點(diǎn)的父節(jié)點(diǎn)是否有右結(jié)點(diǎn)，有的話润樱，如果右結(jié)點(diǎn)未訪問則將其入棧渣触，當(dāng)一個(gè)節(jié)點(diǎn)的左右結(jié)點(diǎn)都已經(jīng)訪問過或者不包含左右結(jié)點(diǎn)，則出棧壹若。
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
Map<TreeNode, Integer> map = new HashMap<>();
Stack<TreeNode> stack = new Stack<>();
if(root == null)
return list;
stack.push(root);
while(!stack.isEmpty()) {
root = stack.peek();
if(root.left == null && root.right == null) {//不含左右結(jié)點(diǎn)時(shí)嗅钻，出棧
root = stack.pop();
list.add(root.val);
map.put(root, 1);
}else if((root.left!=null && root.right == null && map.containsKey(root.left))||(root.right != null && root.left == null && map.containsKey(root.right)) || (root.left != null && root.right != null && map.containsKey(root.left) && map.containsKey(root.right))){//包含子節(jié)點(diǎn)，但是子節(jié)點(diǎn)被訪問過店展，出棧
root = stack.pop();
list.add(root.val);
map.put(root, 1);
}else {
while(root.left != null) {
if(map.containsKey(root.left)) {
break;
}
stack.push(root.left);
root = root.left;
}
if(root.right != null) {
if(map.containsKey(root.right)) {
break;
}
stack.push(root.right);
}
}
}
return list;
}
簡單版非遞歸實(shí)現(xiàn)：后序遍歷的輸出順序是左养篓、右、根赂蕴，當(dāng)我們采用先序遍歷的方法柳弄，但是先遍歷右子樹，實(shí)現(xiàn)的效果是根概说、右碧注、左，剛好和后序遍歷的結(jié)果想法糖赔，所以我們通過add(0, node)的方式將順序反序萍丐，達(dá)到我們想要的效果。
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
Deque<TreeNode> stack = new ArrayDeque<>();
TreeNode node = root;
while(node != null || !stack.isEmpty()) {
if(node != null) {
stack.push(node);
list.add(0, node.val);
node = node.right;
}else {
node = stack.pop();
node = node.left;
}
}
return list;
}
- 層次遍歷：將二叉樹按層輸出挂捻，借助隊(duì)列實(shí)現(xiàn)碉纺。借助null來標(biāo)記一層的結(jié)束船万。當(dāng)讀取到的結(jié)點(diǎn)不是null刻撒，將該結(jié)點(diǎn)的左右結(jié)點(diǎn)入隊(duì)列，當(dāng)讀到null耿导，如果此時(shí)隊(duì)列不空声怔，則繼續(xù)入null標(biāo)志新的一層的結(jié)尾。
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> list = new ArrayList<>();
if(root == null)
return list;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
queue.add(null);
int num = 0;
List<Integer> tempList = new ArrayList<>();
list.add(tempList);
while(!queue.isEmpty()) {
TreeNode temp = queue.poll();
if(temp != null) {
list.get(num).add(temp.val);
if(temp.left != null)
queue.add(temp.left);
if(temp.right != null)
queue.add(temp.right);
}else {
if(!queue.isEmpty()) {
num++;
tempList = new ArrayList<>();
list.add(tempList);
queue.add(null);
}
}
}
return list;
}
參考：
Preorder, Inorder, and Postorder Iteratively Summarization
二叉樹的幾種遍歷遞歸與非遞歸java實(shí)現(xiàn)
