猫不理的锅包肉

前序遍历

先访问根节点再访问其左右子树，这是先序遍历；

144. 二叉树的前序遍历

给定一个二叉树，返回它的 前序 遍历。

 示例:

输入: [1,null,2,3]

   1
    \
     2
    /
   3 

输出: [1,2,3]
进阶: 递归算法很简单，你可以通过迭代算法完成吗？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-preorder-traversal
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

递归法

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var preorderTraversal = function (root) {
    var list = [];

    function recursive(root) {
        if (root) {
            list.push(root.val);
            recursive(root.left);
            recursive(root.right);
        }
    }
    recursive(root);
    return list;
};

迭代法
定义一个栈 每次循环从栈中弹出栈顶 将栈顶的值放入list数组
如果存在右节点则入栈 如果存在左节点则入栈
这里先入栈的是右节点 符合前序遍历先访问根节点后 首先访问左节点再访问右节点的性质
因为栈是先入后出的结构

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var preorderTraversal = function (root) {
    var list = [];
    var stack = [];
    if (!root) return list;
    stack.push(root);
    while (stack.length) {
        var flag = stack.pop();
        list.push(flag.val);
        if (flag.right) stack.push(flag.right)
        if (flag.left) stack.push(flag.left)
    }

    return list;
};

589. N叉树的前序遍历

给定一个 N 叉树，返回其节点值的前序遍历。

例如，给定一个 3叉树 :

返回其前序遍历: [1,3,5,6,2,4]。

说明: 递归法很简单，你可以使用迭代法完成此题吗?

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/n-ary-tree-preorder-traversal
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

递归法

/**
 * // Definition for a Node.
 * function Node(val, children) {
 *    this.val = val;
 *    this.children = children;
 * };
 */

/**
 * @param {Node} root
 * @return {number[]}
 */
var preorder = function (root) {
    var list = [];
    function recursive(root) {
        if (root) {
            list.push(root.val);
            root.children.forEach(element => {
                recursive(element);
            });
        }
    }
    recursive(root);
    return list;
};

迭代法
这个思路和144题的迭代法一致
只是把入栈的操作从rl入栈 变成了 childen倒序入栈

/**
 * // Definition for a Node.
 * function Node(val, children) {
 *    this.val = val;
 *    this.children = children;
 * };
 */

/**
 * @param {Node} root
 * @return {number[]}
 */
var preorder = function (root) {
    var list = [];
    var stack = [];
    if (!root) return list;
    stack.push(root)
    while (stack.length) {
        var flag = stack.pop();
        list.push(flag.val);
        for (let i = flag.children.length - 1; i >= 0; i--) {
            stack.push(flag.children[i])
        }
    }
    return list;
};

中序遍历

按照左子树、根节点、右子树的顺序访问的方式为中序遍历；

94. 二叉树的中序遍历

给定一个二叉树，返回它的中序 遍历。

示例:

输入: [1,null,2,3]

   1
    \
     2
    /
   3

输出: [1,3,2]
进阶: 递归算法很简单，你可以通过迭代算法完成吗？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-inorder-traversal
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

递归法

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var inorderTraversal = function (root) {
    var list = [];

    function recursive(root) {
        if (root) {
            if (root.left) {
                recursive(root.left)
            }
            list.push(root.val)
            if (root.right) {
                recursive(root.right)
            }
        }
    }
    recursive(root);
    return list;
};

迭代法
比较重要的一个点就是要查找当前根节点所有左节点
首先内部循环判断当前节点是否存在 如果存在则当前节点入栈然后 root = root.left 查找最后一个左节点
内部循环之后 stack 栈顶就是最后一个左节点 将它弹出 val 值压入 list
root = root.right 判断右节点是否存在
循环以上步骤

动到当前节点的右节点；下次循环时

// Definition
// for a binary tree node.
function TreeNode(val) {
    this.val = val;
    this.left = this.right = null;
}

var list = new TreeNode(1);
list.right = new TreeNode(2);
list.right.left = new TreeNode(3);


/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var inorderTraversal = function (root) {
    var list = [];
    var stack = [];
    while (root || stack.length) {
        while (root) {
            stack.push(root);
            root = root.left;
        }
        root = stack.pop();
        list.push(root.val);
        root = root.right;
    }
    return list;
};


console.time('程序用时');
console.log(inorderTraversal(list));
console.timeEnd('程序用时');

后序遍历

先访问左右子树，再访问根节点就是后序遍历。

145. 二叉树的后续遍历

给定一个二叉树，返回它的 后序 遍历。

示例:
输入: [1,null,2,3]

   1
    \
     2
    /
   3 

输出: [3,2,1]
进阶: 递归算法很简单，你可以通过迭代算法完成吗？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-postorder-traversal
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var postorderTraversal = function (root) {
    var list = [];

    function recursive(root) {
        if (root) {
            if (root.left) {
                recursive(root.left)
            }
            if (root.right) {
                recursive(root.right)
            }
            list.push(root.val)
        }
    }
    recursive(root);
    return list;
};

590. N叉树的后序遍历

给定一个 N 叉树，返回其节点值的后序遍历。

例如，给定一个 3叉树 :

返回其后序遍历: [5,6,3,2,4,1].

说明: 递归法很简单，你可以使用迭代法完成此题吗?

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/n-ary-tree-postorder-traversal
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

/**
 * // Definition for a Node.
 * function Node(val,children) {
 *    this.val = val;
 *    this.children = children;
 * };
 */

/**
 * @param {Node} root
 * @return {number[]}
 */
var postorder = function (root) {
    var list = [];

    function recursive(root) {
        if (root) {
            root.children.forEach(element => {
                recursive(element);
            });
            list.push(root.val);
        }
    }
    recursive(root);
    return list;
};

层序遍历

从上到下，从左到右的遍历树

102. 二叉树的层序遍历

给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。

示例：
二叉树：[3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

返回其层次遍历结果：

[
  [3],
  [9,20],
  [15,7]
]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-level-order-traversal
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

迭代
宽度优先搜索（BFS）
队列的先进先出非常适合在这里使用。
首先level用来确定层级，queue用来存放数据
首先将root加入队列，相当于手动确定第一层
然后根据队列中已有的节点长度来循环，将队列中的节点的val添加到当前level层级数组中
判断当前层级节点的子节点是否存在，添加到队列中。
因为循环的条件是开始循环前队列的长度，也就是上一层级的所有节点的数量。
所以循环结束时队列剩下的就是下一层级的所有节点，level++进入下一层级

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var inorderTraversal = function (root) {
    if (!root) return [];
    var list = [];
    var queue = [root];
    var level = 0;
    while (queue.length) {
        list.push([]);
        var length = queue.length;
        while (length--) {
            var flag = queue.shift();
            list[level].push(flag.val)
            flag.left && queue.push(flag.left);
            flag.right && queue.push(flag.right);
        }
        level++;
    }
    return list;
};

429. N叉树的层序遍历

给定一个 N 叉树，返回其节点值的层序遍历。 (即从左到右，逐层遍历)。

例如，给定一个 3叉树 :

返回其层序遍历:

[
     [1],
     [3,2,4],
     [5,6]
]

说明:

1.树的深度不会超过 1000。
2.树的节点总数不会超过 5000。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/n-ary-tree-level-order-traversal
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

迭代法
思路和二叉树的层序遍历基本没有差别
只需要将children循环遍历 添加到队列中即可

/**
 * // Definition for a Node.
 * function Node(val,children) {
 *    this.val = val;
 *    this.children = children;
 * };
 */
/**
 * @param {Node} root
 * @return {number[][]}
 */
var levelOrder = function (root) {
    if (!root) return [];
    var list = [];
    var queue = [root];
    var level = 0;
    while (queue.length) {
        list.push([]);
        var length = queue.length;
        while (length--) {
            var flag = queue.shift();
            list[level].push(flag.val)
            for (let i = 0; i < flag.children.length; i++) {
                queue.push(flag.children[i]);
            }
        }
        level++;
    }
    return list;
};