二叉树的应用系列

二叉树应用

Problems

• Tree-Min-Value

// n = # nodes
// time  : O(n)
// space : O(n)
// brute force
// deepth-deep-search
/*const treeMinValues = (root) => {
  let minValue= Infinity;
  const stack = [root];
  while (stack.length > 0){
      const current = stack.pop();
      if (current.val < minValue)
          minValue = current.val;
      if (current.left !== null){
          stack.push(current.left);
      }

      if (current.right !== null){
          stack.push(current.right);
      }
  }

  return minValue;
}*/
// breadth-deep-search
/*const treeMinValues = (root) => {
    let minValue= Infinity;
    const stack = [root];
    while (stack.length > 0){
        const current = stack.shift();
        if (current.val < minValue)
            minValue = current.val;
        if (current.left !== null){
            stack.push(current.left);
        }

        if (current.right !== null){
            stack.push(current.right);
        }
    }

    return minValue;
}*/
// deepth-deep-search && recrusive
const treeMinValues = (root) => {
    if (root === null) return  Infinity;
    const leftMin = treeMinValues(root.left);
    const rightMin = treeMinValues(root.right);
    return Math.min(root.val,leftMin,rightMin);
};


class Node {
    constructor(val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

const a = new Node(19);
const b = new Node(53);
const c = new Node(14);
const e = new Node(-8);
const d = new Node(9);
const f = new Node(-34);

a.left = b;
a.right = c;
b.left = d;
b.right = e;
c.right = f;
let result = treeMinValues(a);
console.log(result);    //-34

• Tree-Sum-Value

// n = # nodes
// time  : O(n)
// space : O(n)
// brute force
/*const treeSumValues = (root) => {
    // base case
    if (root === null) return 0;
    // recrusive call
    return root.val +treeSumValues(root.left) + treeSumValues(root.right);
};*/
// recrusive way 1th
/*const treeSumValues = (root) => {
    // base case
    if (root === null) return 0;
    // recrusive call
    let totalSum = root.val;
    const queue = [root];
    while (queue.length > 0) {
        const current = queue.shift();
        if (current.left !== null) {
            queue.push(current.left);
            totalSum += current.left.val;
        }
        if (current.right !== null) {
            queue.push(current.right);
            totalSum += current.right.val;
        }
    }

    return totalSum;
};*/
// recrusive method 2th
// best practive
const treeSumValues = (root) => {
    // base case
    if (root === null) return 0;
    // recrusive call
    // let totalSum = root.val;
    let totalSum = 0;
    const queue = [root];
    while (queue.length > 0) {
        const current = queue.shift();
        totalSum += current.val;
        if (current.left !== null) {
            queue.push(current.left);
        }
        if (current.right !== null) {
            queue.push(current.right);
        }
    }
    return totalSum;
};


class Node {
    constructor(val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

const a = new Node(1);
const b = new Node(5);
const c = new Node(14);
const e = new Node(8);
const d = new Node(9);
const f = new Node(-34);

a.left = b;
a.right = c;
b.left = d;
b.right = e;
c.right = f;
let result = treeSumValues(a);
console.log(result);    //3

• Max-Path-Sum

// n = # nodes
// time  : O(n)
// space : O(n)
const maxPathSum = (root) => {
    if (root === null) return -Infinity;
    if (root.left === null && root.right === null) return root.val;

    const maxChild = Math.max(
        maxPathSum(root.left),
        maxPathSum(root.right)
    )
    return root.val + maxChild;
}
//ADT

class Node {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

const a = new Node(19);
const b = new Node(53);
const c = new Node(14);
const e = new Node(-8);
const d = new Node(9);
const f = new Node(-34);

a.left = b;
a.right = c;
b.left = d;
b.right = e;
c.right = f;
let result = maxPathSum(a);
console.log(result);  //81