如何在JavaScript中反转二叉树？

Question

如何翻转二叉树？我最近遇到了这个问题，但是我所有试图解决它的尝试都失败了。下面是初始二叉树。

     4
   /   \
  2     7
 / \   / \
1   3 6   9

     4
   /   \
  7     2
 / \   / \
9   6 3   1
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var invertTree = function(root) {
    
};

- Bogdan Zaitsev

---

[root.left, root.right] = [root.right, root.left] 然后对子节点执行相同操作。 - Photon

只需交换左节点和右节点，尝试使用我的二叉树类，其中包含内置函数reverse()。请参考以下链接： 类 - https://www.npmjs.com/package/@dsinjs/binary-tree 文档 - https://dsinjs.github.io/binary-tree/#reverse - Siddhesh Kulkarni

Answer 1

使用深度优先搜索（DFS）的递归方法在js中交换节点会更容易。

    const trav = (currNode) => {
      if (currNode === null) {
        return;
      }
      const temp = currNode.lNode;
      currNode.lNode = currNode.rNode;
      currNode.rNode = temp;
      trav(currNode.lNode);
      trav(currNode.rNode);
    };
    trav(root);
    return root;

更多详情请参考我编写的类，其中包含更有趣的方法-
类 - https://www.npmjs.com/package/@dsinjs/binary-tree
reverse() 方法的文档 - https://dsinjs.github.io/binary-tree/#reverse

- Siddhesh Kulkarni

---

似乎在遍历之后交换值比在之前更清晰。 - tkane2000

Answer 2

对于至少有一个子节点的每个节点，您可以通过将节点的.left值设置为节点的.right值，将节点的.right值设置为（旧的）.left值来交换其子节点。一旦交换了子节点，您可以通过递归调用您的invertTree()函数来查看是否需要对子树进行相同的过程。如果一个节点没有左侧或右侧子节点，那么它是一个叶节点，这意味着您可以返回传入的节点（因为不需要进一步的子节点交换）。

function Node(val, left, right) {
  this.val = (val===undefined ? 0 : val);
  this.left = (left===undefined ? null : left);
  this.right = (right===undefined ? null : right);
}

const invertTree = function(root) {
  if(!root || !root.left && !root.right) { // base case
    return root;
  }
  
  const oldLeft = root.left;
  root.left = root.right;
  root.right = oldLeft;
  invertTree(root.left);
  invertTree(root.right);
  return root;
};


const tree = new Node(4, new Node(2, new Node(1), new Node(3)), new Node(7, new Node(6), new Node(9)));
console.log(invertTree(tree));

- Nick Parsons

Answer 3

您可以通过递归遍历树，如果左右节点存在，则交换它们并对树进行变异。

const invertTree = tree => {
    if (!(tree?.left && tree?.right)) {
        return tree
    }

    [tree.right, tree.left] = [invertTree(tree.left), invertTree(tree.right)]
}

- Richie Bendall

---

一行代码胜过千言万语。 - php_nub_qq

这只适用于完全平衡二叉树，而不适用于任何二叉树。 - undefined

Answer 4

最近对一个答案的编辑使得这个老问题重新浮出水面，我没有看到任何简单的回答来处理不可变数据。所以这里有一个快速函数：

const invertTree = (t) =>
  t === null ? null : new TreeNode (t .val, invertTree (t .right), invertTree (t .left))

const tree = new TreeNode (4, new TreeNode (2, new TreeNode (1), new TreeNode (3)), new TreeNode (7, new TreeNode (6), new TreeNode (9)))

const inverted = invertTree (tree)

// Note that the original is not mutated:
console .log ('Original: ', JSON .stringify (tree, null, 4))
console .log ('Inverted: ', JSON .stringify (inverted, null, 4))

.as-console-wrapper {max-height: 100% !important; top: 0}

<script>function TreeNode (val, left, right) {this .val = (val === undefined ? 0 : val); this .left = (left === undefined ? null : left); this .right = (right === undefined ? null : right)}</script>

在我们的基本情况下，节点是null，我们返回null。否则，我们构造一个具有相同val的新节点，并使用递归调用invertTree传递右节点和左节点，以便新树将它们交换。

如果由我决定，我不会为此使用构造函数（也不会使用class），而是使用简单的数据构造函数：

const node = (val, left, right) => ({val, left: left || null, right: right || null})

const invertTree = (t) =>
  t == null ? null : node (t .val, invertTree (t .right), invertTree (t .left))

const tree = node (4, node (2, node (1), node (3)), node (7, node (6), node (9)))
const inverted = invertTree (tree)

console .log ('Original: ', JSON .stringify (tree, null, 4))
console .log ('Inverted: ', JSON .stringify (inverted, null, 4))

.as-console-wrapper {max-height: 100% !important; top: 0}

- Scott Sauyet

Answer 5

function invertTree(node) {
    if (node && node.left) {
        let left = node.left;
        node.left = node.right;
        node.right = left;
        invertTree(node.right);
        invertTree(node.left);
    }
    return node;
}

const n = {value: 5, left: {left: 5, right: 6 }, right: {left: 1, right: 2}};
console.log(invertTree(n))

- Eme

Answer 6

我是这样解决这个问题的。尝试一下这个算法。 我知道现在有点晚了，但它会帮助其他人的。

 const node = {
    value: 1,
    left: {
      value: 2,
      left: { value: 4  },
       right: { value: 5  }   
    },
    right: {
       value: 3,
       left: { value: 6},
       right: { value: 7  }
    }
 }

invertFree = (node) => {
    if (node) {
        const newNode = { value: node.value }
        if (node.right) {
            newNode.left = invertFree(node.right)
        }
        if (node.left) {
           newNode.right = invertFree(node.left)
        }
        return newNode
    }
}

console.log(invertFree(node))

- Avazkhon