二叉树的前序遍历
返回结果：[‘1’, ‘2’, ‘4’, ‘5’, ‘3’, ‘6’, ‘7’]
144.二叉树的前序遍历 - 迭代算法
给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
示例 1：
输入：root = [1,null,2,3]
输出：[1,2,3]
示例 2：
输入：root = [1,2,3,4,5,null,8,null,null,6,7,9]
输出：[1,2,4,5,6,7,3,8,9]
示例 3：
输入：root = []
输出：[]
示例 4：
输入：root = [1]
输出：[1]
提示：
树中节点数目在范围 [0, 100] 内-100 <= Node.val <= 100
进阶：递归算法很简单，你可以通过迭代算法完成吗？
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function preorderTraversal(root: TreeNode | null): number[] {
if (!root) return []
let arr = []
let stack = [root]
while(stack.length) {
let o = stack.pop()
arr.push(o.val)
o.right && stack.push(o.right)
o.left && stack.push(o.left)
}
return arr
};
二叉树的中序遍历
返回结果：[‘4’, ‘2’, ‘5’, ‘1’, ‘6’, ‘3’, ‘7’]
94.二叉树的中序遍历
给定一个二叉树的根节点 root ，返回它的中序遍历 。
示例 1：
输入：root = [1,null,2,3]
输出：[1,3,2]
示例 2：
输入：root = []
输出：[]
示例 3：
输入：root = [1]
输出：[1]
提示：
树中节点数目在范围 [0, 100] 内
-100 <= Node.val <= 100
进阶: 递归算法很简单，你可以通过迭代算法完成吗？
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function inorderTraversal(root: TreeNode | null): number[] {
let arr = []
let stack = []
let o = root
while(stack.length || o) {
while(o) {
stack.push(o)
o = o.left
}
let n = stack.pop()
arr.push(n.val)
o = n.right
}
return arr
};
二叉树的后序遍历
返回结果：[‘4’, ‘5’, ‘2’, ‘6’, ‘7’, ‘3’, ‘1’]
145.二叉树的后序遍历
给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。
示例 1：
输入：root = [1,null,2,3]
输出：[3,2,1]
示例 2：
输入：root = [1,2,3,4,5,null,8,null,null,6,7,9]
输出：[4,6,7,5,2,9,8,3,1]
示例 3：
输入：root = []
输出：[]
示例 4：
输入：root = [1]
输出：[1]
提示：
树中节点的数目在范围 [0, 100] 内-100 <= Node.val <= 100
进阶：递归算法很简单，你可以通过迭代算法完成吗？
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function postorderTraversal(root: TreeNode | null): number[] {
if (!root) return []
let arr = []
let stack = [root]
while(stack.length) {
let o = stack.pop()
arr.unshift(o.val)
o.left && stack.push(o.left)
o.right && stack.push(o.right)
}
return arr
};
111.二叉树的最小深度
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明：叶子节点是指没有子节点的节点。
示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：2
示例 2：
输入：root = [2,null,3,null,4,null,5,null,6]
输出：5
提示：
树中节点数的范围在 [0, 105] 内-1000 <= Node.val <= 1000
/**
* 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 minDepth = function(root) {
if (!root) return 0
let stack = [[root,1]]
while( stack.length ) {
let [o,n] = stack.shift()
if (!o.left && !o.right) {
return n
}
if (o.left) stack.push([o.left, n+1])
if (o.right) stack.push([o.right, n+1])
}
};
104.二叉树的最大深度
给定一个二叉树 root ，返回其最大深度。
二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：3
示例 2：
输入：root = [1,null,2]
输出：2
提示：
树中节点的数量在 [0, 104] 区间内。-100 <= Node.val <= 100
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function maxDepth(root: TreeNode | null): number {
if (!root) return 0
let stack = [root]
let num = 0
while(stack.length) {
let len = stack.length
num++
while(len--) {
let o = stack.shift()
o.left && stack.push(o.left)
o.right && stack.push(o.right)
}
}
return num
};
226.翻转二叉树
给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
示例 1：
输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]
示例 2：
输入：root = [2,1,3]
输出：[2,3,1]
示例 3：
输入：root = []
输出：[]
提示：
树中节点数目范围在 [0, 100] 内
-100 <= Node.val <= 100
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function invertTree(root: TreeNode | null): TreeNode | null {
if (root === null) return null
let tmp = root.left
root.left = root.right
root.right = tmp
invertTree(root.left)
invertTree(root.right)
return root
};
100.相同的树
给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
示例 1：
输入：p = [1,2,3], q = [1,2,3]
输出：true
示例 2：
输入：p = [1,2], q = [1,null,2]
输出：false
示例 3
输入：p = [1,2,1], q = [1,1,2]
输出：false
提示：
两棵树上的节点数目都在范围 [0, 100] 内
-104 <= Node.val <= 104
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function isSameTree(p: TreeNode | null, q: TreeNode | null): boolean {
if (p === null && q === null) return true
if (p === null || q === null) return false
if (p.val !== q.val) return false
return isSameTree(p.left, q.left) && isSameTree(p.right, q.right)
};