二叉树的中序遍历

二叉树的中序遍历LeetCode94
题目：给定一个二叉树的根节点 root ，返回 它的 中序 遍历
输入：root = [1,null,2,3] 输出：[1,3,2]
输入：root = [] 输出：[]

二叉树的前、中、后序遍历是对根节点而言，即根节点的遍历顺序，都可以使用递归或者迭代的方式
使用循环的方式时，先将左字数都push到数组中，当左子树遍历完成后取出最近的节点，然后遍历该节点的右子树

  1. // 使用while循环
  2. var inorderTraversal = function (root) {
  3.   const result = []
  4.   if (root === null) return result;
  5.   const queue = [];
  6.   let p = root;
  7.   while (p || queue.length > 0) {
  8.     if (p !== null) {
  9.       queue.push(p);
  10.       p = p.left;
  11.       continue;
  12.     } 
  13.     p = queue.pop();
  14.     result.push(p.val);
  15.     p = p.right;
  16.   }
  17.   return result;
  18. };
  20. // 使用递归
  21. var inorderTraversal = function (root) {
  22.   const result = []
  23.   if (root === null) return result;
  24.   function traverse(root) {
  25.     if (root.left !== null) {
  26.       traverse(root.left)
  27.     }
  28.     result.push(root.val);
  29.     if (root.right !== null) {
  30.       traverse(root.right);
  31.     }
  32.   }
  33.   traverse(root);
  34.   return result;
  35. };

二叉树的层序遍历

二叉树的层序遍历LeetCode102
题目：给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）
输入：root = [3,9,20,null,null,15,7] 输出：[[3],[9,20],[15,7]]
输入：root = [] 输出：[]
输入：root = [1] 输出：[[1]]

层序遍历即一层一层的遍历二叉树，遍历当前层的数组，拿到value，并将当前层的左右子树都存入另一个数组，如此循环

  1. var levelOrder = function(root) {
  2.   const result = [];
  3.   if (root === null) return result;
  4.   let currentLevel = [root];
  6.   while(currentLevel.length > 0) {
  7.     const nextLevel = []
  8.     const currentLevelResult = currentLevel.map(item => {
  9.       if (item.left) {
  10.         nextLevel.push(item.left)
  11.       }
  12.       if (item.right) {
  13.         nextLevel.push(item.right)
  14.       }
  15.       return item.val;
  16.     });
  17.     result.push(currentLevelResult);
  18.     currentLevel = nextLevel;
  19.   }
  20.   return result;
  21. };

从前序与中序遍历构造二叉树

从前序与中序遍历构造二叉树LeetCode105
题目：给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] 输出: [3,9,20,null,null,15,7]
输入: preorder = [-1], inorder = [-1] 输出: [-1]

前序遍历的数组的特征：[根节点，左子树前序遍历，右子树前序遍历]，中序遍历的数组的特征：[左子树中序遍历，根节点，右子树中序遍历]，只要找到根节点，就能划分左右子树
先构造根节点，并根据根节点将中序遍历数组划分为左右子树，递归遍历，中序遍历数组的左子树遍历完成时，前序遍历数组的左子树根节点已经全部移出，继续遍历右子树

  1. var buildTree = function (preorder, inorder) {
  2.   const traverse = function (subInorder) {
  3.     if (subInorder.length === 0) {
  4.       return null
  5.     }
  6.     const rootValue = preorder.shift();
  7.     const root = new TreeNode(rootValue);
  8.     const temp = subInorder.findIndex(value => value === rootValue);
  9.     if (temp === -1) {
  10.       return null;
  11.     }
  13.     root.left = traverse(subInorder.slice(0, temp));
  14.     root.right = traverse(subInorder.slice(temp + 1, subInorder.length));
  15.     return root;
  16.   }
  17.   const root = traverse(inorder);
  18.   return root;
  19. };

从中序与后序遍历构造二叉树

从中序与后序遍历构造二叉树LeetCode106
题目：给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。
输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3] 输出：[3,9,20,null,null,15,7]
输入：inorder = [-1], postorder = [-1] 输出：[-1]

与上一题类似，不过后序遍历数组结枸是[左子树后序遍历数组，右子树后序遍历数组，根节点]，所以构造二叉树的时候是先构造根节点，再构造右子树，然后再构造左子树

  1. var buildTree = function(inorder, postorder) {
  2.   const traverse = function (subInorder) {
  3.     if (subInorder.length === 0) return null;
  4.     const rootValue = postorder.pop();
  5.     const root = new TreeNode(rootValue);
  6.     const temp = subInorder.findIndex(value => rootValue === value);
  7.     if (temp === -1) return null;
  8.     root.right = traverse(subInorder.slice(temp + 1, subInorder.length));
  9.     root.left = traverse(subInorder.slice(0, temp));
  10.     return root;
  11.   }
  12.   const root = traverse(inorder);
  13.   return root;
  14. };

二叉树的最近公共祖先

二叉树的最近公共祖先LeetCode236
题目：给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 输出：3
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4 输出：5
输入：root = [1,2], p = 1, q = 2 输出：1

中心思想是先判断根节点的左右子树与p，q是否存在父子关系，如果左子树与右子树均存在父子关系，则最近的公共祖先就肯定是根节点了，如果只有左子树存在父子关系，返回左子树，如果只有右子树存在父子关系，返回右节点
为了确保返回的左右节点和根节点是距离p,q最近的，需要先递归到左右子树的最下面的节点，然后一层一层网上判断，类似于后续遍历

  1. var lowestCommonAncestor = function (root, p, q) {
  2.   if (root === null) {
  3.     return null;
  4.   }
  5.   if (p === root || q === root) {
  6.     return root;
  7.   }
  8.   const leftNode = lowestCommonAncestor(root.left, p, q);
  9.   const rightNode = lowestCommonAncestor(root.right, p, q);
  11.   // 如果leftNode与rightNode均有值，则返回他们的根节点
  12.   if (leftNode !== null && rightNode !== null) {
  13.     return root;
  14.   }
  15.   // 如果leftNode没有值，则p或q在右节点上，返回右节点
  16.   if (leftNode === null) {
  17.     return rightNode;
  18.   }
  19.   // 如果rightNode没有值，则p或者q在左节点上，返回左节点
  20.   if (rightNode === null) {
  21.     return leftNode;
  22.   }
  23. };