js 二叉树的相关算法

1、求二叉树所有的到达末端节点路径
这是二叉树结构。我们用递归方法实现。

二叉树.jpeg

var n4 = {value: 4, left: null, right: null};
var n5 = {value: 5, left: null, right: null};
var n6 = {value: 6, left: null, right: null};
var n2 = {value: 2, left: n4, right: n5};
var n3 = {value: 3, left: n6, right: null};
var n1 = {value: 1, left: n2, right: n3};
var binaryTreePaths = function(root) {
console.log(root);
    if (root === null) return [];
    if (root.left === null && root.right === null) {
      return [root.value.toString()];
    }
    var left = binaryTreePaths(root.left),
        right = binaryTreePaths(root.right);
    return left.concat(right).map(x => root.value + '->' + x);
  };
binaryTreePaths(n1);

结果是： ["1->2->4", "1->2->5", "1->3->6"]
2、二叉树镜像反转

二叉树反转.jpeg

var invertTree = function(root) {   
   if(root==null){return null;}
    //获取左子树
    var d1=invertTree(root.left);
    //获取右子树
    var d2=invertTree(root.right);
    //调整左右
    root.left=d2;
    root.right=d1;
    return root;
};
invertTree(n1);