二叉树

发表于

递归

前序遍历

1
2
3
4
5
6
7
8
9
10
11
var preorderTraversal(root){
    const res=[];
    function _preorder(node){
        if(!node)return ;
       	res.push(node.val);
        _preorder(node.left);
        _preorder(node.right);
    }
    _preorder(root);
    return res;
}

中序遍历

1
2
3
4
5
6
7
8
9
10
var preorderTraversal(root){
    const res=[];
    function _preorder(node){
        if(!node)return ;
        _preorder(node.left);                                                                                                           res.push(node.val);
        _preorder(node.right);
    }
    _preorder(root);
    return res;
}

后序遍历

1
2
3
4
5
6
7
8
9
10
var preorderTraversal(root){
    const res=[];
    function _preorder(node){
        if(!node)return ;
        _preorder(node.right);
        _preorder(node.left);                                                                                                           res.push(node.val);
    }
    _preorder(root);
    return res;
}

迭代

前序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
var preorderTraversal=function (root){
    if(!root) return ;
    const stack=[root];
    const res=[];
    while(stack.length){
        const cur =stack.pop();
        res.push(cur.val);        
        cur.right&&stack.push(cur.right)
        cur.left&&stack.push(cur.left)
    }
    return res
    
}

中序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
var inorderTraversal=function(root){
	if(!root) return ;
    const stack=[];
    let cur=root;
    const res=[];
    while(stack.length||cur){                                                                                                   		//左节点先压入栈
        while(cur){
            stack.push(cur);
            cur=cur.left;
        }        
        const node=stack.pop();
        res.push(node.val);
        if(node.right!=null){
            cur=node.right;
        }        
    }
    return res;
}