迭代遍历二叉树

题目描述：给定一个二叉树，返回它的前序（先序）遍历序列。

示例:
输入: [1,null,2,3]

1   
 \   
  2   
 /  
3 

输出: [1,2,3]
进阶: 递归算法很简单，你可以通过迭代算法完成吗？

先序遍历

const root = {
    val: 'A',
    left: {
        val: 'B',
        left: {
            val: 'D'
        },
        right: {
            val: 'E'
        }
    },
    right: {
        val: 'C',
        right: {
            val: 'F'
        },
    }
}

function preorder(root) {
  const res = [];
  if (!root) return res;
  const stack = [];
  stack.push(root);

  while (stack.length) {
    const cur = stack.pop();
    res.push(cur.val);

    if (cur.right) {
      stack.push(cur.right)
    }

    if (cur.left) {
      stack.push(cur.left);
    }
  }

  return res;
}

console.log(preorder(root)); // ["A", "B", "D", "E", "C", "F"]

后序遍历

const root = {
    val: 'A',
    left: {
        val: 'B',
        left: {
            val: 'D'
        },
        right: {
            val: 'E'
        }
    },
    right: {
        val: 'C',
        right: {
            val: 'F'
        },
    }
}

function postorder(root) {
  const res = [];
  if (!root) return res;
  const stack = [];
  stack.push(root);

  while (stack.length) {
    const cur = stack.pop();
    res.unshift(cur.val);

    if (cur.left) {
      stack.push(cur.left);
    }

    if (cur.right) {
      stack.push(cur.right);
    }
  }
  return res;
}

console.log(postorder(root)) // ["D", "E", "B", "F", "C", "A"]

中序遍历

const root = {
    val: 'A',
    left: {
        val: 'B',
        left: {
            val: 'D'
        },
        right: {
            val: 'E'
        }
    },
    right: {
        val: 'C',
        right: {
            val: 'F'
        },
    }
}

function inorder(root) {
    const res = [];
    const stack = [];
    let cur = root;
    while (cur || stack.length) {
        while (cur) {
            stack.push(cur)
            cur = cur.left;
        }
        cur = stack.pop();
        res.push(cur.val);
        cur = cur.right;
    }
    return res;
}

console.log(inorder(root)) // ["D", "B", "E", "A", "C", "F"]

层序遍历的衍生问题

题目描述：给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。

示例：
二叉树：[3,9,20,null,null,15,7]

  3
 / \
9  20
  /  \
 15   7

返回其层次遍历结果：

[
[3],
[9,20],
[15,7]
]

function fn(root) {
  const res = [];
  
  if (!root) return res;

  const queue = [];
  queue.push(root);

  while (queue.length) {
    const level = [];
    const len = queue.length;

    for (let i = 0; i < len; i++) {
      const top = queue.shift();
      level.push(top.val);
      
      if (top.left) {
        queue.push(top.left);
      }

      if (top.right) {
        queue.push(top.right);
      }
    }
    res.push(level);
  }
  return res;
}

翻转二叉树

题目描述：翻转一棵二叉树。

示例：
输入：

     4
   /   \
  2     7
 / \   / \
1   3 6   9

输出：

     4
   /   \
  7     2
 / \   / \
9   6 3   1

const root = {
  val: 4,
  left: {
    val: 2,
    left: {
      val: 1
    },
    right:{
      val: 3
    }
  },
  right: {
    val: 7,
    left: {
      val: 6
    },
    right: {
      val: 9
    }
  }
}
function invertTree(root) {
  if (!root) return root;
  const left = invertTree(root.left);
  const right = invertTree(root.right);
  root.left = right;
  root.right = left;
  return root;
}