二叉树的非递归遍历

发表于 | 分类于

思路

非递归遍历需要用到辅助的栈来存储需要遍历的节点。

前序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function first(root) {
  var arr=[],res=[];
  if(root!=null){
      arr.push(root);
  }
  while(arr.length!=0){
      var temp=arr.pop();
      res.push(temp.val);
      //这里先放右边再放左边是因为取出来的顺序相反
      if(temp.right!=null){
          arr.push(temp.right);
      }
      if(temp.left!=null){
          arr.push(temp.left);
      }
  }
  return res;
}

中序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function LDR(root){

var arr=[],res=[];
while(true){
    while(root!=null){
        arr.push(root);
        root=root.left;
    }
    //终止条件：最后树遍历完了自然就结束
    if(arr.length==0){
        break;
    }
    var temp=arr.pop();
    res.push(temp.val);
    root=temp.right;
}
return res;
}
LDR(root)//4,2,5,1,6,3,7

后续遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function LRD(root){

var arr=[],res=[];
arr.push(root);
while(arr.length!=0){
    var p=arr.pop();
    res.push(p.val);
    if(p.left!=null){
        arr.push(p.left);
    }
    if(p.right!=null){
        arr.push(p.right);
    }
}
return res.reverse();
}
LRD(root)//4,5,2,6,7,3,1