二叉树

二叉树反转

function invertTree(root) {
    // 如果当前节点为空，则直接返回
    if (!root) {
        return null;
    }

    // 交换当前节点的左右子节点
    [root.left, root.right] = [root.right, root.left];

    // 递归地反转左右子树
    invertTree(root.left);
    invertTree(root.right);

    // 返回反转后的根节点
    return root;
}

// 示例：创建一个简单的二叉树
//     4
//    / \
//   2   7
//  / \ / \
// 1  3 6  9
const root = {
    val: 4,
    left: {
        val: 2,
        left: { val: 1, left: null, right: null },
        right: { val: 3, left: null, right: null }
    },
    right: {
        val: 7,
        left: { val: 6, left: null, right: null },
        right: { val: 9, left: null, right: null }
    }
};

// 反转二叉树
invertTree(root);

// 打印反转后的二叉树
function printTree(node) {
    if (node === null) {
        return;
    }
    console.log(node.val);
    printTree(node.left);
    printTree(node.right);
}

printTree(root); // 输出：4 7 9 6 2 3 1

类型以下二叉树层级蛇形输出

​ 2 4 5 7 9 11 13

输出结果为：2 4 5 13 11 9 7

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

function zigzagLevelOrder(root) {
    if (!root) return [];

    let result = [];
    let queue = [root];
    let leftToRight = true; // 用于控制遍历方向

    while (queue.length > 0) {
        let levelSize = queue.length;
        let level = [];

        for (let i = 0; i < levelSize; i++) {
            let currentNode = queue.shift();

            // 根据当前层的遍历方向决定添加到数组的位置
            if (leftToRight) {
                level.push(currentNode.value);
            } else {
                level.unshift(currentNode.value);
            }

            // 将子节点加入队列
            item.left && queue.push(item.left);
            item.right && queue.push(item.right);
        }

        // 反转遍历方向
        leftToRight = !leftToRight;
        result.push(...level);
    }

    // 将所有层级的结果合并成一个数组
    return result.flat();
}

// 构建示例二叉树
let root = new TreeNode(2);
let root = new TreeNode(2);
root.left = new TreeNode(4);
root.right = new TreeNode(5);
root.left.left = new TreeNode(7);
root.left.right = new TreeNode(9);
root.right.left = new TreeNode(11);
root.right.right = new TreeNode(13);

// 执行蛇形层级遍历
console.log(zigzagLevelOrder(root)); // 输出: [2, 4, 5, 13, 11, 9, 7]

104. 二叉树的最大深度

示例 1： 输入：root = [3,9,20,null,null,15,7] 输出：3

示例 2： 输入：root = [1,null,2] 输出：2

解法1

dfs 深度遍历 从左开始 递归终止调节 1、空 返回 1(当前深度) + dfs(left) 中的最大值dfs(right)

var maxDepth = function(root) {
    if(root) return 0;
    return 1 + Matn.max(maxDepth(root.left),maxDepth(root.right))

};

103. 二叉树的锯齿形层序遍历

示例 1： 输入：root = [3,9,20,null,null,15,7] 输出：[[3],[20,9],[15,7]]

示例 2： 输入：root = [1] 输出：[[1]]

示例 3： 输入：root = [] 输出：[]

解法1

空 返回 1、res 记录值，queue存树 2、flag反转 3、1循环，queue有，新的list记录树的value， 4、2循环取queue中的值，list添加， queue看看有没有左右叶子 5、flag变化 res记录list

var zigzagLevelOrder = function(root) {
    const res = [],queue = [root]
    let flag = true;
    if(!root) return res;
    while(queue.length > 0) {
        const size = queue.length;
        const list = [];
        const key = flag ? 'push': 'unshift'
        for(let i = 0 ;i<size;i++){
            const r = queue.shift();
            list[key](r.val);
            if(r.left) queue.push(r.left);
            if(r.right) queue.push(r.right);
        }
        flag=!flag;
        res.push(list)
    }
    return res;
};

二叉树前序遍历

function preorderTraversal(root) {
  const result = [];
  function traverse(node) {
    if (!node) return;
    result.push(node.value);
    traverse(node.left);
    traverse(node.right);
  }
  traverse(root);
  return result;
}