js binary tree All In One

二叉树 / binary tree

前序遍历：根节点、左节点、右节点（1、2、4、5、7、8、3、6）
中序遍历：左节点、根节点、右节点（4、2、7、5、8、1、3、6）
后序遍历：左节点、右节点、根节点（4、7、8、5、2、6、3、1）

112. Path Sum

112. 路径总和

https://leetcode.com/problems/path-sum/
https://leetcode-cn.com/problems/path-sum

1. DFS 深度优先算法

/**
 * 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
 * @param {number} targetSum
 * @return {boolean}
 */
var hasPathSum = function(root, targetSum) {
  if(!root) {
    // no exist root node
    return false;
  }
  if(!root.left && !root.right) {
     // is leaf node
    return targetSum === root.val;
  } else {
    const sum = targetSum - root.val;
    // DFS 深度优先算法
    return hasPathSum(root.left, sum) || hasPathSum(root.right, sum);
  } 
};

/**
 * 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
 * @param {number} targetSum
 * @return {boolean}
 */
var hasPathSum = function(root, targetSum) {
  if(!root) {
    // no exist root node
    return false;
  }
  if(!root.left && !root.right) {
     // is leaf node
    return targetSum === root.val;
  } else {
    // DFS 深度优先算法
    return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val);
  } 
};

2. BFS 广度优先算法

/**
 * 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
 * @param {number} targetSum
 * @return {boolean}
 */
var hasPathSum = function(root, targetSum) {
  if(!root) {
    // no exist root node
    return false;
  }
  // BFS 广度优先算法
  const nodeQueue = [root];
  const sumQueue = [root.val];
  // 队列不空
  while(nodeQueue.length) {
     let node = nodeQueue.pop();
     let total = sumQueue.pop();
     // is leaf node
    if(!node.left && !node.right && targetSum === total) {
      return true;
    } else {
      if(node.left) {
        nodeQueue.push(node.left);
        sumQueue.push(node.left.val + total);
      }
      if(node.right) {
        nodeQueue.push(node.right);
        sumQueue.push(node.right.val + total);
      }
    }
  }
  return false;
};

var hasPathSum = function(root, targetSum) {
  if(!root) {
    // no exist root node
    return false;
  }
  // BFS 广度优先算法
  const nodeQueue = [root];
  const sumQueue = [root.val];
  // 队列不空
  while(nodeQueue.length) {
     let node = nodeQueue.shift();
     let total = sumQueue.shift();
     // let node = nodeQueue.pop();
     // let total = sumQueue.pop();
     // is leaf node
    if(!node.left && !node.right) {
      if(targetSum === total) {
         return true;
      } else {
        // const temp = total - node.value;
        // nodeQueue.pop();
        // sumQueue.pop();
        // sumQueue.push(temp);
        continue;
      }
    } else {
      if(node.left) {
        nodeQueue.push(node.left);
        // ?  val !== value
        sumQueue.push(node.value + total);
      }
      if(node.right) {
        nodeQueue.push(node.right);
        // ?  val !== value
        sumQueue.push(node.value + total); 
      }
    }
  }
  return false;
};

257. Binary Tree Paths

257. 二叉树路径

https://leetcode.com/problems/binary-tree-paths/

https://leetcode-cn.com/problems/binary-tree-paths/

var binaryTreePaths = function (root) {
    const result = [];
    const traverseTree = (node, path) => {
        if(!node.left && !node.right) {
            path += node.val;
            // leaf node
            result.push(path);
            return;
        } else {
            path += node.val + '->';
        }
        if(node.left) {
            traverseTree(node.left, path);
        }
        if(node.right) {
            traverseTree(node.right, path);
        }
        // 不需要 返回值
        // return path;
    };
    // DFS 深度优先算法
    traverseTree(root, '');
    return result;
};

var binaryTreePaths = function (root) {
    const result = [];
    const traverseTree = (node, path) => {
        if(!node.left && !node.right) {
            path += node.val;
            // leaf node
            result.push(path);
        } else {
            path += node.val + '->';
        }
        if(node.left) {
            traverseTree(node.left, path);
        }
        if(node.right) {
            traverseTree(node.right, path);
        }
        return path;
    };
    // DFS 深度优先算法
    traverseTree(root, '');
    return result;
};

/**
 * 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 {string[]}
 */
var binaryTreePaths = function (root) {
    const result = [];
    const path = [];
    function findPath (node) {
        if(node == null) {
            return;
        };
        path.push(node.val);
        if(!node.left && !node.right) {
            result.push(path.join('->'));
        }
        findPath(node.left);
        findPath(node.right);
        // 删除已访问的 child node value
        path.pop();
    }
    // DFS
    findPath(root);
    return result;
};

refs

https://github.com/xgqfrms/learning/issues/120

?xgqfrms 2012-2020

www.cnblogs.com/xgqfrms 发布文章使用：只允许注册用户才可以访问！

原创文章，版权所有??xgqfrms, 禁止转载 ???，侵权必究??！