二叉樹的前中后序遍歷
核心思想：用堆疊來實作對節點的存盤，一邊遍歷，一邊將節點入堆疊，在需要時將節點從堆疊中取出來并遍歷該節點的左子樹或者右子樹，重復上述程序，當堆疊為空時，遍歷完成，
前序遍歷
//非遞回
//根 左 右
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
//用陣列來存盤前序遍歷結果
List<Integer> list = new ArrayList<>();
if(root==null) return list;
//創建一個堆疊
Stack<TreeNode> st = new Stack<>();
//cur指向根節點
TreeNode cur = root;
while(!st.isEmpty()||cur!=null){
//一邊向左遍歷，一邊將遍歷到的節點入堆疊，節點值入陣列
while(cur!=null){
list.add(cur.val);
st.push(cur); //根
cur=cur.left; //左
}
//指標指向堆疊頂節點（即上一個節點），并將堆疊頂節點出堆疊
cur = st.pop();
//指標指向該節點的右子樹，開始下一輪的遍歷
cur = cur.right; //右
}
return list;
}
}
中序遍歷
//非遞回
//左 根 右
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
if(root==null) return list;
Stack<TreeNode> st = new Stack<>();
TreeNode cur = root;
while(!st.isEmpty()||cur!=null){
//一邊向左遍歷，一邊將遍歷到的節點入堆疊
while(cur!=null){
st.push(cur);
cur = cur.left; //左
}
cur = st.pop();
//存盤遍歷結果
list.add(cur.val); //根
cur = cur.right; //右
}
return list;
}
}
前序遍歷和中序遍歷的代碼基本相同，但是后序遍歷與它們不太一樣
后序遍歷
//非遞回
//左 右 根
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
if(root==null) return list;
TreeNode cur = root;
//關鍵在于定義一個cur的前驅節點
TreeNode pre = null;
Stack<TreeNode> st = new Stack<>();
while(cur!=null||!st.isEmpty()){
//一邊向左遍歷，一邊將遍歷到的節點入堆疊
while(cur!=null){
st.push(cur);
cur = cur.left;
}
cur = st.pop();
//若該節點的右節點為空，或者右節點被遍歷過，陣列才能存盤該節點的數值（也就是我們最后才遍歷的根）
if(cur.right==null||cur.right==pre){
list.add(cur.val);
pre = cur;
cur=null;
}else{//如果不滿足，說明該節點的右節點還沒有被遍歷過，那么接著向右子節點遍歷
st.push(cur);
cur=cur.right;
}
}
return list;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/300459.html
標籤：java