树

二叉树的先序，中序，后序遍历

先序遍历表示先访问根节点，然后访问左节点，最后访问右节点。

中序遍历表示先访问左节点，然后访问根节点，最后访问右节点。

后序遍历表示先访问左节点，然后访问右节点，最后访问根节点。

递归实现

递归实现相当简单，代码如下

  1. function TreeNode(val) {
  2.   this.val = val;
  3.   this.left = this.right = null;
  4. }
  5. var traversal = function(root) {
  6.   if (root) {
  7.     // 先序
  8.     console.log(root); 
  9.     traversal(root.left);
  10.     // 中序
  11.     // console.log(root); 
  12.     traversal(root.right);
  13.     // 后序
  14.     // console.log(root);
  15.   }
  16. };

对于递归的实现来说，只需要理解每个节点都会被访问三次就明白为什么这样实现了。

非递归实现

非递归实现使用了栈的结构，通过栈的先进后出模拟递归实现。

以下是先序遍历代码实现

  1. function pre(root) {
  2.   if (root) {
  3.     let stack = [];
  4.     // 先将根节点 push
  5.     stack.push(root);
  6.     // 判断栈中是否为空
  7.     while (stack.length > 0) {
  8.       // 弹出栈顶元素
  9.       root = stack.pop();
  10.       console.log(root);
  11.       // 因为先序遍历是先左后右，栈是先进后出结构
  12.       // 所以先 push 右边再 push 左边
  13.       if (root.right) {
  14.         stack.push(root.right);
  15.       }
  16.       if (root.left) {
  17.         stack.push(root.left);
  18.       }
  19.     }
  20.   }
  21. }

以下是中序遍历代码实现

  1. function mid(root) {
  2.   if (root) {
  3.     let stack = [];
  4.     // 中序遍历是先左再根最后右
  5.     // 所以首先应该先把最左边节点遍历到底依次 push 进栈
  6.     // 当左边没有节点时，就打印栈顶元素，然后寻找右节点
  7.     // 对于最左边的叶节点来说，可以把它看成是两个 null 节点的父节点
  8.     // 左边打印不出东西就把父节点拿出来打印，然后再看右节点
  9.     while (stack.length > 0 || root) {
  10.       if (root) {
  11.         stack.push(root);
  12.         root = root.left;
  13.       } else {
  14.         root = stack.pop();
  15.         console.log(root);
  16.         root = root.right;
  17.       }
  18.     }
  19.   }
  20. }

以下是后序遍历代码实现，该代码使用了两个栈来实现遍历，相比一个栈的遍历来说要容易理解很多

  1. function pos(root) {
  2.   if (root) {
  3.     let stack1 = [];
  4.     let stack2 = [];
  5.     // 后序遍历是先左再右最后根
  6.     // 所以对于一个栈来说，应该先 push 根节点
  7.     // 然后 push 右节点，最后 push 左节点
  8.     stack1.push(root);
  9.     while (stack1.length > 0) {
  10.       root = stack1.pop();
  11.       stack2.push(root);
  12.       if (root.left) {
  13.         stack1.push(root.left);
  14.       }
  15.       if (root.right) {
  16.         stack1.push(root.right);
  17.       }
  18.     }
  19.     while (stack2.length > 0) {
  20.       console.log(s2.pop());
  21.     }
  22.   }
  23. }

中序遍历的前驱后继节点

实现这个算法的前提是节点有一个 parent 的指针指向父节点，根节点指向 null 。

树 - 图1

如图所示，该树的中序遍历结果是 4, 2, 5, 1, 6, 3, 7

前驱节点

对于节点 2 来说，他的前驱节点就是 4 ，按照中序遍历原则，可以得出以下结论

  1. 如果选取的节点的左节点不为空，就找该左节点最右的节点。对于节点 1 来说，他有左节点 2 ，那么节点 2 的最右节点就是 5
  2. 如果左节点为空，且目标节点是父节点的右节点，那么前驱节点为父节点。对于节点 5 来说，没有左节点，且是节点 2 的右节点，所以节点 2 是前驱节点
  3. 如果左节点为空，且目标节点是父节点的左节点，向上寻找到第一个是父节点的右节点的节点。对于节点 6 来说，没有左节点，且是节点 3 的左节点，所以向上寻找到节点 1 ，发现节点 3 是节点 1 的右节点，所以节点 1 是节点 6 的前驱节点

以下是算法实现

  1. function predecessor(node) {
  2.   if (!node) return 
  3.   // 结论 1
  4.   if (node.left) {
  5.     return getRight(node.left)
  6.   } else {
  7.     let parent = node.parent
  8.     // 结论 2 3 的判断
  9.     while(parent && parent.right === node) {
  10.       node = parent
  11.       parent = node.parent
  12.     }
  13.     return parent
  14.   }
  15. }
  16. function getRight(node) {
  17.   if (!node) return 
  18.   node = node.right
  19.   while(node) node = node.right
  20.   return node
  21. }

后继节点

对于节点 2 来说，他的后继节点就是 5 ，按照中序遍历原则，可以得出以下结论

  1. 如果有右节点，就找到该右节点的最左节点。对于节点 1 来说，他有右节点 3 ，那么节点 3 的最左节点就是 6
  2. 如果没有右节点，就向上遍历直到找到一个节点是父节点的左节点。对于节点 5 来说，没有右节点，就向上寻找到节点 2 ，该节点是父节点 1 的左节点，所以节点 1 是后继节点

以下是算法实现

  1. function successor(node) {
  2.   if (!node) return 
  3.   // 结论 1
  4.   if (node.right) {
  5.     return getLeft(node.right)
  6.   } else {
  7.     // 结论 2
  8.     let parent = node.parent
  9.     // 判断 parent 为空
  10.     while(parent && parent.left === node) {
  11.       node = parent
  12.       parent = node.parent
  13.     }
  14.     return parent
  15.   }
  16. }
  17. function getLeft(node) {
  18.   if (!node) return 
  19.   node = node.left
  20.   while(node) node = node.left
  21.   return node
  22. }

树的深度

树的最大深度：该题目来自 Leetcode，题目需要求出一颗二叉树的最大深度

以下是算法实现

  1. var maxDepth = function(root) {
  2.     if (!root) return 0 
  3.     return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1
  4. };

对于该递归函数可以这样理解：一旦没有找到节点就会返回 0，每弹出一次递归函数就会加一，树有三层就会得到3。