二叉樹(shù)的前中后序迭代寫(xiě)法
既然是迭代，肯定需要用到棧，那么如何思考3種遍歷方法是怎么運(yùn)用棧的呢？
前序遍歷，就是先根節(jié)點(diǎn)，再左孩子，然后右孩子。
一開(kāi)始我們把根節(jié)點(diǎn)放進(jìn)棧里。然后就彈出來(lái)VISIT，這樣確保了先訪問(wèn)了根節(jié)點(diǎn)。根據(jù)棧后進(jìn)先出的特性，這時(shí)我們需要先把右孩子放進(jìn)棧里，然后是左孩子。
下面是代碼
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
Stack<TreeNode> st = new Stack<>();
if(root==null) return res;
st.push(root);
while(!st.isEmpty()){
TreeNode cur = st.pop();
res.add(cur.val);
if(cur.right!=null) st.push(cur.right);
if(cur.left!=null) st.push(cur.left);
}
return res;
}
前序遍歷的思考軌跡還是比較容易。下面是中序遍歷。中序遍歷要求先左孩子然后是根節(jié)點(diǎn)。所以當(dāng)根節(jié)點(diǎn)放進(jìn)去的時(shí)候，不應(yīng)該立刻出來(lái)。因?yàn)樽蠛⒆觾?yōu)先。那么就一路向左，一條路走到黑，左到不能左。這里有一個(gè)門(mén)檻，就是如果到左了，下面就把最左的彈出來(lái)。這個(gè)時(shí)候如果是WHILE循環(huán)，那么棧頂?shù)淖笥謺?huì)因?yàn)橐宦废蜃蟮拇a，又把左孩子塞回去。那么就是個(gè)死循環(huán)。錯(cuò)誤代碼如下
while(!st.isEmpty()){
while(st.peek().left!=null)
st.push(st.peek().left);
TreeNode cur = st.pop();
res.add(cur.val);
if(cur.right!=null) st.push(cur.right);
}
為了避免上述情況，我們需要額外一個(gè)NODE節(jié)點(diǎn)，當(dāng)做CUR。然后通過(guò)CUR節(jié)點(diǎn)，來(lái)防止使用棧頂節(jié)點(diǎn)來(lái)走一路向左的邏輯。下面就會(huì)產(chǎn)生正確代碼。
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
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();
res.add(cur.val);
cur = cur.right;
}
return res;
}
最后我們來(lái)思考后序遍歷，就是先左孩子，后右孩子，最后是根節(jié)點(diǎn)。那么我們還是借用中序遍歷的思想，一路做到底，利用一個(gè)CUR節(jié)點(diǎn)。但是左到低之后，還要看有沒(méi)有右孩子，如果有右孩子，還需先把右孩子處理下。如果沒(méi)有，就可以訪問(wèn)當(dāng)前節(jié)點(diǎn)了。不難得出如下錯(cuò)誤代碼
while(!st.isEmpty() || cur!=null){
while(cur != null){
st.push(cur);
cur = cur.left;
}
if(st.peek().right !=null){
cur = st.peek().right;
}else{
res.add(st.pop().val);
}
}
這里就是把右節(jié)點(diǎn)放到棧里。隨后出棧。隨后ST.PEEK右節(jié)點(diǎn)又不為空了。那么這個(gè)右節(jié)點(diǎn)就反復(fù)進(jìn)出。為了避免這種情況，我們需要引入一個(gè)lastvisit 的節(jié)點(diǎn)。來(lái)切斷這個(gè)情況。如果右節(jié)點(diǎn)不為空，并且LASTVISIT 不是這個(gè)右節(jié)點(diǎn)。那么才去指向右節(jié)點(diǎn)。不然就接著POP。
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
TreeNode lastVisit = null;
Stack<TreeNode> st = new Stack<>();
TreeNode cur = root;
while(!st.isEmpty() || cur!=null){
while(cur!=null){
st.push(cur);
cur = cur.left;
}
cur = st.peek();
if(cur.right==null || lastVisit==cur.right){
res.add(cur.val);
lastVisit = st.pop();
cur=null;
}else{
cur = cur.right;
}
}
return res;
}
綜上我們已經(jīng)說(shuō)完了常規(guī)的遍歷套路。可以看到前序遍歷，只要一個(gè)棧。中序遍歷需要一個(gè)棧和一個(gè)CUR節(jié)點(diǎn)。后序遍歷需要一個(gè)棧，一個(gè)CUR節(jié)點(diǎn)，還需要一個(gè)LASTVISIT節(jié)點(diǎn)。
模擬系統(tǒng)棧的遍歷方法
前序遍歷
class Command {
String cmd;
TreeNode r;
public Command(String c,TreeNode r){
cmd = c;
this.r = r;
}
}
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
Stack<Command> st = new Stack<>();
st.push(new Command("go",root));
while(!st.isEmpty()){
Command cmd = st.pop();
if(cmd.r == null) continue;
if("go".equals(cmd.cmd)){
st.push(new Command("go",cmd.r.right));
st.push(new Command("go",cmd.r.left));
st.push(new Command("print",cmd.r));
}else if("print".equals(cmd.cmd)){
res.add(cmd.r.val);
}
}
return res;
}
中序遍歷
class Command {
String cmd;
TreeNode r;
public Command(String c,TreeNode r){
cmd = c;
this.r = r;
}
}
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
Stack<Command> st = new Stack<>();
st.push(new Command("go",root));
while(!st.isEmpty()){
Command cmd = st.pop();
if(cmd.r == null) continue;
if("go".equals(cmd.cmd)){
st.push(new Command("go",cmd.r.right));
st.push(new Command("print",cmd.r));
st.push(new Command("go",cmd.r.left));
}else if("print".equals(cmd.cmd)){
res.add(cmd.r.val);
}
}
return res;
}
后序遍歷
class Command {
String cmd;
TreeNode r;
public Command(String c,TreeNode r){
cmd = c;
this.r = r;
}
}
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
Stack<Command> st = new Stack<>();
st.push(new Command("go",root));
while(!st.isEmpty()){
Command cmd = st.pop();
if(cmd.r == null) continue;
if("go".equals(cmd.cmd)){
st.push(new Command("print",cmd.r));
st.push(new Command("go",cmd.r.right));
st.push(new Command("go",cmd.r.left));
}else if("print".equals(cmd.cmd)){
res.add(cmd.r.val);
}
}
return res;
}
怎么不用棧來(lái)實(shí)現(xiàn)二叉樹(shù)的前中后序遍歷
106. Construct Binary Tree from Inorder and Postorder Traversal
首先用后序的最后一個(gè)，去把中序的隊(duì)列切開(kāi)。然后遞歸。
public TreeNode buildTree(int[] inorder, int[] postorder) {
int l = postorder.length;
if(l==0) return null;
int i=0;
for(;i<inorder.length;i++){
if(inorder[i] == postorder[l-1]) break;
}
TreeNode root = new TreeNode(postorder[l-1]);
root.left = buildTree(Arrays.copyOfRange(inorder,0,i),Arrays.copyOfRange(postorder,0,i));
root.right = buildTree(Arrays.copyOfRange(inorder,i+1,l),Arrays.copyOfRange(postorder,i,l-1));
return root;
}
