树的操作

[1684838553]

144. 二叉树的前序遍历

根左右

示例 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

来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/binary-tree-preorder-traversal 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

/**
 * 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, result = []) {
    if(!root) {
        return result
    }
    result.push(root.val)
    if(root.left) preorderTraversal(root.left, result)
    if(root.right) preorderTraversal(root.right, result)
    return result
};

[1684838553]

94. 二叉树的中序遍历

左根右

给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。 

示例 1：

输入：root = [1,null,2,3] 输出：[1,3,2] 示例 2：

输入：root = [] 输出：[] 示例 3：

输入：root = [1] 输出：[1]

来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/binary-tree-inorder-traversal 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

/**
 * 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, result=[]) {
    if(!root){
        return result
    }
    inorderTraversal(root.left, result)
    result.push(root.val)
    inorderTraversal(root.right, result)
    return result
};   

[1684838553]

145. 二叉树的后序遍历

左右根

给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。

 

示例 1：

输入：root = [1,null,2,3] 输出：[3,2,1] 示例 2：

输入：root = [] 输出：[] 示例 3：

输入：root = [1] 输出：[1]

来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/binary-tree-postorder-traversal 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

/**
 * 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, result =[]) {
    if(!root){
        return result
    }
    postorderTraversal(root.left, result)
    postorderTraversal(root.right, result)
    result.push(root.val)

    return result
};

[1684838553]

104. 二叉树的最大深度

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

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

3

/ \ 9 20 / \ 15 7 返回它的最大深度 3 。

来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/maximum-depth-of-binary-tree 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

/**
 * 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) {
    //使用递归的方法 递归三部曲
    //1. 确定递归函数的参数和返回值
    const getDepth=function(node){
    //2. 确定终止条件
        if(node===null){
            return 0;
        }
    //3. 确定单层逻辑
        let leftDepth=getDepth(node.left);
        let rightDepth=getDepth(node.right);
        let depth=1+Math.max(leftDepth,rightDepth);
        return depth;
    }
    return getDepth(root);
};

[1684838553]

有一棵二叉树，每个节点由一个大写字母标识(最多26个节点）。现有两组字母，分别表示前序遍历（父节点->左孩子->右孩子）和中序遍历（左孩子->父节点->右孩子）的结果，请你输出后序遍历（左孩子->右孩子->父节点）的结果。

输入 每个输入文件包含两串字母，各占一行。（每串只包含大写字母） 第一行字母表示前序遍历结果，第二行字母表示中序遍历结果。

输出 输出仅一行，表示后序遍历的结果，结尾换行。

样例 输入样例 1 复制

DBACEGF ABCDEFG 输出样例 1

ACBFGED

// please define the JavaScript input here(you can also rewrite the input). 
// following is the default: 
process.stdin.resume();
process.stdin.setEncoding('utf-8');
let input = '';
process.stdin.on('data', (data) => {
  input += data;
});
process.stdin.on('end', () => {
  let inputArray = input.split('\n');
  // please finish the function body here.       
  // please define the JavaScript output here. For example: console.log(result);
  const before = inputArray[0]
  const middle = inputArray[1]

  const tree = getTree(before, middle)
  let res = ''
  const result = post(tree)
  console.log(result.join(''))
  process.exit();
});

function TreeNode(val){
    this.val = val
    this.left = null
    this.right = null
}

function getTree(before, middle){
    if(!before.length) return
    const root_val = before[0]
    const index = middle.indexOf(root_val);
    let tree = new TreeNode(root_val)
    tree.left = getTree(before.slice(1,index+1), middle.slice(0,index))
    tree.right = getTree(before.slice(index+1), middle.slice(index+1))
    return tree
}

function post(tree, res = []){
    if(!tree) return res
    tree.left && post(tree.left, res)
    tree.right && post(tree.right, res)
    res.push(tree.val)
    return res
}

方法二

// please define the JavaScript input here(you can also rewrite the input). 
// following is the default: 
process.stdin.resume();
process.stdin.setEncoding('utf-8');
let input = '';
process.stdin.on('data', (data) => {
  input += data;
});
process.stdin.on('end', () => {
  let inputArray = input.split('\n');
  // please finish the function body here.       
  // please define the JavaScript output here. For example: console.log(result);
  const before = inputArray[0]
  const middle = inputArray[1]

  const result = getTree(before, middle)
  console.log(result.join(''))
  process.exit();
});

let res = []
function getTree(before, middle){
    if(!before.length) return res
    const root_val = before[0]
    const index = middle.indexOf(root_val);
    getTree(before.slice(1,index+1), middle.slice(0,index))
    getTree(before.slice(index+1), middle.slice(index+1))
    res.push(root_val)
    return res
}