image.png

理论基础

1. 种类：完全二叉树和满二叉树（主要）
   完全二叉树：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2^(h-1) 个节点。

   
   
   image.png

满二叉树：
满二叉树：如果一棵二叉树只有度为0的结点和度为2的结点，并且度为0的结点在同一层上，则这棵二叉树为满二叉树。

image.png

二叉树的前中后序遍历

• 144.二叉树的前序遍历
• 145.二叉树的后序遍历
• 94.二叉树的中序遍历

//前序遍历
var preorderTraversal = function(root) {
    let arr=[]
    var dfs=function(node){
        if(!node){
            return
        }
        arr.push(node.val)
        if(node.left){
            dfs(node.left)
        }
        if(node.right){
            dfs(node.right)
        }
    }
    dfs(root)
    return arr
};
//后序遍历
var postorderTraversal = function(root) {
    let arr=[]
    var dfs=function(node){
        if(!node){
            return
        }
        if(node.left){
            dfs(node.left)
        }
        if(node.right){
            dfs(node.right)
        }
        arr.push(node.val)

    }
    dfs(root)
    return arr
};
//中序遍历
var inorderTraversal = function(root) {
    let arr=[]
    var dfs=function(node){
        if(!node){
            return
        }
        if(node.left){
            dfs(node.left)
        }
        arr.push(node.val)

        if(node.right){
            dfs(node.right)
        }

    }
    dfs(root)
    return arr
};

迭代法

说明：由于中序遍历的顺序与处理的顺序不同，先访问中间节点，而最先处理左节点，与前序遍历不同，前序遍历，遍历顺序与处理顺序一致。后序遍历，可借助前序遍历实现。

1. 前序遍历
   前序遍历是中左右，每次先处理的是中间节点，那么先将根节点放入栈中，然后将右孩子加入栈，再加入左孩子。

var preorderTraversal = function(root) {
    let res = [];
  let stack = [root];
  while (stack.length) {
    let node = stack.pop()
    if(!node) continue;
    res.push(node.val)
    stack.push(node.right)
     stack.push(node.left)
  }
  return res
};

2. 后序遍历
   与前序遍历不同的是：先将根节点放入栈中，然后将左孩子加入栈，再将右孩子加入栈，最后反转。

var postorderTraversal = function(root) {
    let arr=[]
     let res = [];
  let stack = [root];
  while (stack.length) {
    let node = stack.pop()
    if(!node) continue;
    res.push(node.val)
     stack.push(node.left)
    stack.push(node.right)

  }
  return res.reverse()
};

3. 中序遍历

var inorderTraversal = function(root) {
    let res=[]
    let stack=[]
    let cur = root
    while(cur || stack.length){
        if(cur){
            stack.push(cur)
            cur=cur.left
        }else{
            cur = stack.pop()
            res.push(cur.val)
            cur=cur.right
        }
    }
    return res
};

二叉树遍历统一迭代法待后续补充