二叉树
来源：leetbook-二叉树
更多资料：
树的遍历
前序遍历
给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
示例 1：
输入：root = [1,null,2,3] 输出：[1,2,3] 示例 2：
输入：root = [] 输出：[] 示例 3：
输入：root = [1] 输出：[1] 示例 4：
输入：root = [1,2] 输出：[1,2] 示例 5：
输入：root = [1,null,2] 输出：[1,2]
提示：
树中节点数目在范围 [0, 100] 内 -100 <= Node.val <= 100
进阶：递归算法很简单，你可以通过迭代算法完成吗？
解法：
/**
* 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 {number[]}
*/
var preorderTraversal = function(root) {
if(root == null) return []
let result = []
let order = (node, arr) => {
if (node == null) return
let { left, right, val } = node
arr.push(val)
order(left, arr)
order(right, arr)
}
order(root, result)
return result
}
中序遍历
给定一个二叉树的根节点 root ，返回它的 中序 遍历。
示例 1：
输入：root = [1,null,2,3] 输出：[1,3,2] 示例 2：
输入：root = [] 输出：[] 示例 3：
输入：root = [1] 输出：[1] 示例 4：
输入：root = [1,2] 输出：[2,1] 示例 5：
输入：root = [1,null,2] 输出：[1,2]
提示：
树中节点数目在范围 [0, 100] 内 -100 <= Node.val <= 100
进阶: 递归算法很简单，你可以通过迭代算法完成吗？
解法：
/**
* 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 {number[]}
*/
var inorderTraversal = function(root) {
if (root == null) return []
let result = []
let order = (node, arr) => {
if (node == null) return
let { left, right, val } = node
order(left, arr)
arr.push(val)
order(right, arr)
}
order(root, result)
return result
};
后序遍历
给定一个二叉树，返回它的 后序 遍历。
示例:
输入: [1,null,2,3]
1
2 / 3
输出: [3,2,1] 进阶: 递归算法很简单，你可以通过迭代算法完成吗？
解法：
/**
* 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 {number[]}
*/
var postorderTraversal = function(root) {
if (root == null) return []
const res = []
const order = (node, arr) => {
if (node == null) return
const { left, val, right } = node;
order(left, arr)
order(right, arr)
arr.push(val)
}
order(root, res)
return res
};
树的层序遍历
给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。
示例： 二叉树：[3,9,20,null,null,15,7],
3
/
9 20 /
15 7 返回其层序遍历结果：
[ [3], [9,20], [15,7] ]
解法：
var levelOrder = function(root) {
//二叉树的层序遍历
let res=[],queue=[];
queue.push(root);
if(root===null){
return res;
}
while(queue.length!==0){
// 记录当前层级节点数
let length=queue.length;
//存放每一层的节点
let curLevel=[];
for(let i=0;i<length;i++){
let node=queue.shift();
curLevel.push(node.val);
// 存放当前层下一层的节点
node.left&&queue.push(node.left);
node.right&&queue.push(node.right);
}
//把每一层的结果放到结果数组
res.push(curLevel);
}
return res;
};
树的递归
二叉树的最大深度
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例： 给定二叉树 [3,9,20,null,null,15,7]，
3
/
9 20 /
15 7 返回它的最大深度 3 。
解法：
/**
* 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 {number}
*/
var maxDepth = function(root) {
let res = 0;
const dfs = (node, depth) => {
if (node == null) return
if (node.left == null && node.right == null) {
res = Math.max(res, depth)
}
dfs(node.left, depth + 1)
dfs(node.right, depth + 1)
}
dfs(root, res);
return res
};
方法2：
/**
* 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 {number}
*/
var maxDepth = function(root) {
if (!root) {
return 0
} else {
const left = maxDepth(root.left);
const right = maxDepth(root.right);
return Math.max(left, right) + 1
}
};
对称二叉树
给定一个二叉树，检查它是否是镜像对称的。
例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
1
/
2 2 / \ /
3 4 4 3
但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
1
/
2 2 \
3 3
进阶：
你可以运用递归和迭代两种方法解决这个问题吗？
解法：
/**
* 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 {boolean}
*/
var isSymmetric = function(root) {
if (root == null) return true
const dfs = (left, right) => {
if (left == null && right == null) {
return true
}
if (left == null || right == null) {
return false
}
if (left.val !== right.val) {
return false
}
return dfs(left.left, right.right) && dfs(left.right, right.left)
}
return dfs(root.left, root.right)
};
方法2：
/**
* 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 {boolean}
*/
var isSymmetric = function(root) {
return check(root, root)
};
function check(left, right) {
if (!left && !right) return true
if (!left || !right) return false
return left.val === right.val && check(left.left, right.right) && check(left.right, right.left)
}