【数据结构】二叉树

[miracles1919]

两种解法：

• 遍历：用一个 traverse 函数配合外部变量
• 分解问题：定义一个递归函数，通过子问题（子树）的答案推导出原问题的答案

参考：

• 东哥带你刷二叉树（纲领篇）
• 东哥带你刷二叉树（思路篇）

[miracles1919]

前序、中序、后序

function traverse(root){
  if (root === null) return 

  // 前序位置
  traverse(root.left)
  // 中序位置
  traverse(root.right)
  // 后序位置
}

[miracles1919]

226. 翻转二叉树

• 前序遍历

var invertTree = function(root) {
    traverse(root)
    return root
};

function traverse(root) {
    if (root === null) return

    let temp = root.right
    root.right = root.left
    root.left = temp

    traverse(root.left)
    traverse(root.right)
}

• 分解问题

// 定义：返回翻转后的二叉树的根节点
var invertTree = function(root) {
    if(root === null) return null

    const left = invertTree(root.left)
    const right = invertTree(root.right)
    root.left = right
    root.right = left
    return root 
};

[miracles1919]

116. 填充每个节点的下一个右侧节点指针

var connect = function(root) {
    if (root === null) return null
    traverse(root.left, root.right)
    return root
};

function traverse(node1, node2) {
    if (node1 === null || node2 === null) {
        return null
    }

    node1.next = node2
    traverse(node1.left, node1.right)
    traverse(node2.left, node2.right)
    // 跨父节点的子节点
    traverse(node1.right, node2.left)
}

层序遍历

var connect = function(root) {
    if (root === null) return root

    const queue = [root]

    while (queue.length) {
        const size = queue.length

        for (let i = 0; i < size; i++) {
            const node = queue.shift()

            if (i < size - 1) {
                node.next = queue[0]
            }

            if (node.left) {
                queue.push(node.left)
            }

            if (node.right) {
                queue.push(node.right)
            }
        }
    }

    return root
};

[miracles1919]

114. 二叉树展开为链表

• 分解问题

  // 定义：将以root为根的树展开为一个单链表
  var flatten = function(root) {
  if (root === null) return null
  
  flatten(root.left)
  flatten(root.right)
  
  // 后序遍历位置
  // 左右子树已是一条链表
  const left = root.left
  const right = root.right
  
  // 左子树作为右子树
  root.left = null
  root.right = left
  
  // 右子树接到当前右子树的末端
  let curr = root
  while(curr.right !== null) {
      curr = curr.right
  }
  curr.right = right
  
  return root
  };

• 其他解法，参考

var flatten = function(root) {
    const r = root

    while (root) {
        let node = root.left
        if (node) {
            while(node.right) node = node.right
            // 处理左子树
            node.right = root.right
            root.right = root.left
            root.left = null
        }
        root = root.right
    }

    return r
};