查找某个节点的路径的方法通常有两种，一种是递归算法,另一种是非递归算法

目录

• 以中序遍历为例
• • 递归算法
  • 非递归算法
• 前序、中序、后序
• • 递归写法
  • 非递归写法

以中序遍历为例

1、定义树节点

class TreeNode{
    
    constructor(value){
    
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

2、构建树

// 构建树
let root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
console.log(root);//如下图

递归算法

// 递归中序遍历二叉树
function midOrder(root) {
     
    if(!root || !(root instanceof TreeNode)){
    
        return;
    }
    //instanceof 运算符用于检测构造函数的 prototype 属性是否出现在某个实例对象的原型链上。
    // 递归访问左子树
    midOrder(root.left);
    console.log(root.value);
    // 递归访问右子树
    midOrder(root.right);
}
midOrder(root);

非递归算法

// 非递归中序遍历二叉树
function midOrderN(root) {
     
    let p = root; // p为当前遍历的节点， 初始为根
    let arr = []; // arr作为栈
    while(p || arr.length !== 0){
    
        if(p){
    
            // 遍历左子树
            arr.push(p);
            // 每遇到非空二叉树先向左走
            p = p.left;
        }else{
    
            // p为空，出栈
            let node = arr.pop();
            // 访问该节点
            console.log(node.value);
            // 向右走一次
            p = node.right;
        }
    }
 }
 midOrderN(root)

前序、中序、后序

以下为牛客网的试题

递归写法

function TreeNode(x){
    
    this.val=val;
    this.left=null;
    this.right=null;
}
// 递归方法
function threeOrders(root){
    
    let preArray=[],middleArray=[],lastArray=[];
    //先序遍历：根、左、右
    function preOrder(root){
    
        if(root){
    
            preArray.push(root.val);
            preOrder(root.left);
            preOrder(root.right);
        }
    }
    //中序遍历 ： 左 根 右   
    function inOrder(root){
    
            if(root){
    
                inOrder(root.left)
                middleArray.push(root.val);
                inOrder(root.right);
            }
    }
    //后序遍历：左右根
    function lastOrder(root){
    
        if(root){
    
            lastOrder(root.left);
            lastOrder(root.right);
            lastArray.push(root.val);
        }
    }
    preOrder(root);
    inOrder(root);
    lastOrder(root);
    return [preArray,middleArray,lastArray]
}

非递归写法

function threeOrders(root){
    
    //非递归算法实现先序遍历二叉树，根左右，所以向数组中push一个元素
    function preOrder(root){
    
        let res=[],
        stack=[root];
        while(stack.length>0){
    
            let node=stack.pop();
            res.push(node.val);
            if(node.right){
    
                stack.push(node.right);
            }
            if(node.left){
    
                stack.push(node.right);
            }

        }
        return res;
    }
    //非递归算法 实现中序遍历二叉树   首先遍历找到最深层的左子树，
    function inOrder(root){
    
        let res=[],
            stack=[];
            while(root||stack.length>0){
    
                while(root){
    
                    stack.push(root);
                    root=root.left;
                }
                root=stack.pop();
                res.push(root.val);
                root=root.right;
            }
            return res;
    }
    // 非递归算法实现后序遍历二叉树， 和先序遍历二叉树类似，唯一区别是向数组中unshift元素，先push左再push右
    function lastOrder(root){
    
        let res=[],
        stack=[root];
        while(stack.length>0){
    
            let node=stack.pop();
            res.unshift(node.val);
            if(node.left){
    
                stack.push(node.left);
            }
            if(node.right){
    
                stack.push(node.right);
            }
        }
        return res;
    }
}