二叉树

节点构造函数

function Node(key) {
    this.key = key;
    this.left = null;
    this.right = null;
}
function binaryTree() {
    this.root = null;
}

先序遍历

//先序遍历递归方法
binaryTree.prototype.preOrder = function(node) {
    if (node !== null) {
        console.log(node.key); //先打印当前结点
        this.preOrder(node.left); //打印左结点
        this.preOrder(node.right); //打印右结点
    }
}

//先序遍历非递归方法
//首先将根节点入栈，如果栈不为空，取出节点打印key值，然后依次取右节点和左节点入栈，依次重复
binaryTree.prototype.preOrder2 = function(node) {
    let stack = [];
    stack.push(node);
    while (stack.length > 0) {
        let n = stack.pop();
        console.log(n.key);
        if (n.right != null) {
            stack.push(n.right);
        }
        if (n.left != null) {
            stack.push(n.left);
        }
    }
}

中序遍历

//中序遍历递归方法
binaryTree.prototype.inOrder = function(node) {
    if (node !== null) {
        this.inOrder(node.left);
        console.log(node.key);
        this.inOrder(node.right);
    }
}

//中序遍历非递归方法
//依次取左节点入栈直到左下角节点入栈完毕，弹出节点打印key,如果该节点有右子节点，将其入栈
binaryTree.prototype.inOrder2 = function(node) {
    let stack = [];
    while (node != null || stack.length) {
        if (node != null) {
            stack.push(node);
            node = node.left;
        } else {
            let n = stack.pop();
            console.log(n.key);
            node = n.right;
        }
    }
}

后序遍历

binaryTree.prototype.postOrder = function(node) {
    if (node !== null) {
        this.inOrder(node.left);
        this.inOrder(node.right);
        console.log(node.key);
    }
}

// 后序遍历（迭代法）
function postorderTraversal(root: TreeNode | null): number[] {
    let helperStack: TreeNode[] = [];
    let res: number[] = [];
    let curNode: TreeNode;
    if (root === null) return res;
    helperStack.push(root);
    while (helperStack.length > 0) {
        curNode = helperStack.pop()!;
        res.push(curNode.val);
        if (curNode.left !== null) helperStack.push(curNode.left);
        if (curNode.right !== null) helperStack.push(curNode.right);
    }
    return res.reverse();
};

层序遍历

var levelOrder = function(root) {
    const result = []
    const queue = []
    if (!root) return result
    queue.push(root)
    while(queue.length) {
        const size = queue.length;
        let curLevel = []
        for(let i = 0; i < size; i++) {
            const node = queue.shift();
            curLevel.push(node.val)
            if (node.left) {
                queue.push(node.left)
            }
            if (node.right) {
                queue.push(node.right)
            }
        }
        result.push(curLevel)
    }
    return result;
};

二叉树最大深度

// 迭代法，层序遍历
var maxDepth = function(root) {
    const queue = []
    let depth = 0;
    if (!root) return depth
    queue.push(root)
    while(queue.length) {
        depth++
        const size = queue.length;
        for(let i = 0; i < size; i++) {
            const node = queue.shift();
            if (node.left) {
                queue.push(node.left)
            }
            if (node.right) {
                queue.push(node.right)
            }
        }
    }
    return depth;
};

// 递归法
var maxDepth = function(root) {
    if (root === null) return 0;
    return 1 + Math.max(maxDepth(root.left), maxDepth(root.right))
};

最近公共祖先

1. 使用递归遍历所有节点，如果一个节点的左右子树中同时含有 p 和 q，则它就是最近公共祖先。

2. 递归终止条件有两种：

1. 递归分别下探到左右子节点，同时获取他们的返回值，返回值存在两种情况：

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
var lowestCommonAncestor = function (root, p, q) {
  // 如果root不存在，直接退出循环
  // 如果查询到p或q，则将其返回，供上层递归判断
  if (!root || root === p || root === q) {
    return root;
  }

  // 获取在子树中匹配到的p和q节点
  const left = lowestCommonAncestor(root.left, p, q);
  const right = lowestCommonAncestor(root.right, p, q);

  // 如果p和q同时匹配到，当前节点即为最近公共祖先
  if (left && right) {
    return root;
  }

  // 如果没有同时匹配到p和q，就将匹配到的节点返回给上层判断
  // 最近公共祖先是其本身的情况，会通过该步骤返回
  return left || right;
};

相同的树

var isSameTree = function(p, q) {
    if (!p && !q) return true;  // 如果两个二叉树都为空，则两个二叉树相同
    if (!p || !q) return false; // 如果两个二叉树中有且只有一个为空，则两个二叉树一定不相同。
    if (p.val !== q.val) return false; // 如果两个二叉树都不为空，那么首先判断它们的根节点的值是否相同，若不相同则两个二叉树一定不同 若相同，再分别判断两个二叉树的左子树是否相同以及右子树是否相同
    // if (p.val === q.val 
    return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
};

对称二叉树

var isSymmetric = function(root) {
    // 使用递归遍历左右子树 递归三部曲
    // 1. 确定递归的参数 root.left root.right和返回值true false 
    const compareNode = function(left, right) {
        // 2. 确定终止条件 空的情况
        if(left === null && right !== null || left !== null && right === null) {
            return false;
        } else if(left === null && right === null) {
            return true;
        } else if(left.val !== right.val) {
            return false;
        }
        // 3. 确定单层递归逻辑
        let outSide = compareNode(left.left, right.right);
        let inSide = compareNode(left.right, right.left);
        return outSide && inSide;
    }
    if(root === null) {
        return true;
    }
    return compareNode(root.left, root.right);
};

var sortedArrayToBST = function(nums) {
		let n = nums.length
    if (!n) {
        return null
    }
    let mid = Math.floor(n / 2)
    let root = new TreeNode(nums[mid])

    root.left = sortedArrayToBST(nums.slice(0, mid))
    root.right = sortedArrayToBST(nums.slice(mid + 1, n))

    return root
};

路径总和

var hasPathSum = function(root, targetSum) {
    if (!root) return false;
    // 叶子节点 判断当前的值是否等于 sum 即可
    if (!root.left && !root.right) {
        return root.val === targetSum
    }
    const left = hasPathSum(root.left, targetSum - root.val)
    const right = hasPathSum(root.right, targetSum - root.val)
    return left || right;
};

let pathSum = function (root, sum) {
  if (!root) return 0
  return (
    countSum(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum)
  )
}

let countSum = (node, sum) => {
  let count = 0
  let dfs = (node, target) => {
    if (!node) return

    // 这里拿到结果不能直接return 要继续向下考虑
    // 比如下面的两个节点是 1, -1 那么它们相加得 0 也能得到一个路径
    if (node.val === target) {
      count += 1
    }

    dfs(node.left, target - node.val)
    dfs(node.right, target - node.val)
  }
  dfs(node, sum)
  return count
}