树

# 树

[TOC]

# 一、二叉树

思路：自顶向下自底向上；递归遍历；特况一般。

特况要考虑root为null、root.left为null或root.right为null的情况。

递归参数不要出现left、right，因为会出现left和right不同时有的情况。

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */

1
2
3
4
5
6
7

# 1.1 leetcode-100-相同的树

给定两个二叉树，编写一个函数来检验它们是否相同。如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

/**
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {boolean}
 */
var isSameTree = function(p, q) {
    if(!p && !q) return true
    if(!p && q) return false
    if(p && !q) return false
    if(p.val === q.val) return isSameTree(p.left, q.left) && isSameTree(p.right, q.right)
    else return false
};

1
2
3
4
5
6
7
8
9
10
11
12

# 1.2 leetcode-101-对称二叉树

给定一个二叉树，检查它是否是镜像对称的。

/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isSymmetric = function (root) {
    return isMirror(root, root)

    function isMirror(tree1, tree2) {
        // 1. 特况
        if (!tree1 && !tree2) return true
        if (!tree1 || !tree2) return false

        // 2. 一般
        return (tree1.val === tree2.val) && isMirror(tree1.right, tree2.left) && isMirror(tree2.right, tree1.left)
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# 1.3 leetcode-104-二叉树的最大深度

给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。说明: 叶子节点是指没有子节点的节点。

/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxDepth = function(root, deep=0) {
    if(!root) return deep
    else deep++
    return Math.max(maxDepth(root.left, deep), maxDepth(root.right, deep))
};

1
2
3
4
5
6
7
8
9

# 1.4 leetcode-107-二叉树的层次遍历II

给定一个二叉树，返回其节点值自底向上的层次遍历。（即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrderBottom = function(root) {
    let res = []
    if(root === null) return res
    let val = [], nextNode = [], node = [root]
    while(node.length) {
        val = []
        nextNode = []
        node.forEach(item => {
            val.push(item.val)
            if(item.left!==null) {
                nextNode.push(item.left)
            }
            if(item.right!==null) {
                nextNode.push(item.right)
            }
        })
        res.unshift(val)
        node = nextNode
    }
    return res
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

# 1.5 leetcode-110-平衡二叉树

给定一个二叉树，判断它是否是高度平衡的二叉树。本题中，一棵高度平衡二叉树定义为：一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1。

/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isBalanced = function (root) {
    // 要么返回左右子树的相对高度，要么返回-1表明不是平衡树
    function recur(root) {
        if (root === null) return 0
        let left = recur(root.left)
        if (left === -1) return -1
        let right = recur(root.right)
        if (right === -1) return -1
        if (Math.abs(left - right) >= 2) {
            return -1
        } else {
            return Math.max(left, right) + 1
        }
    }

    return recur(root) !== -1
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

# 1.6 leetcode-111-二叉树的最小深度

给定一个二叉树，找出其最小深度。最小深度是从根节点到最近叶子节点的最短路径上的节点数量。说明: 叶子节点是指没有子节点的节点。

/**
 * @param {TreeNode} root
 * @return {number}
 */
var minDepth = function (root) {
    if (!root) return 0
    return findMin(root, 1)

    function findMin(tree, depth) {
        if (!tree.left && !tree.right) return depth
        if (!tree.left && tree.right) return findMin(tree.right, depth + 1)
        if (tree.left && !tree.right) return findMin(tree.left, depth + 1)
        return Math.min(findMin(tree.left, depth + 1), findMin(tree.right, depth + 1))
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# 1.7 leetcode-112-路径总和

给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。

var hasPathSum = function (root, sum) {
  if (!root) return false
  sum -= root.val
  if (!root.left && !root.right) return sum === 0
  return hasPathSum(root.left, sum) || hasPathSum(root.right, sum)
};

1
2
3
4
5
6

# 1.8 leetcode-226-翻转二叉树

翻转一棵二叉树。

var invertTree = function (root) {
  if(!root) return root
  let left = null, right = null
  if(root.left) left = root.lleeft
  if(root.right) right = root.right
  if (!left && !right) return root
  root.left = invertTree(right)
  root.right = invertTree(left)
  return root
};

1
2
3
4
5
6
7
8
9
10

# 1.9 leetcode-235-二叉搜索树的最近公共祖先

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

说明:

所有节点的值都是唯一的。
p、q 为不同节点且均存在于给定的二叉搜索树中。

var lowestCommonAncestor = function(root, p, q) {
    // 利用二叉搜索树的性质
    // 根结点比两个结点大，就在左子树找
    // 根结点比两个结点小，就在右子树找
    // 否则，返回根结点
    if(root.val > p.val && root.val > q.val) return lowestCommonAncestor(root.left, p, q)
    if(root.val < p.val && root.val < q.val) return lowestCommonAncestor(root.right, p, q)
    return root
};

1
2
3
4
5
6
7
8
9

# 1.10 leetcode-257-二叉树的所有路径

给定一个二叉树，返回所有从根节点到叶子节点的路径。

var binaryTreePaths = function(root) {
  if(!root) return []
  if(!root.left && !root.right) return [root.val.toString()]
  let left = binaryTreePaths(root.left)
  let right = binaryTreePaths(root.right)
  return left.concat(right).map(item => root.val+'->'+item)
};

1
2
3
4
5
6
7

# 1.11 重建二叉树

题目输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

前序遍历：根左右；中序遍历：左根右。

解法

/* function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
} */
function reConstructBinaryTree(pre, vin)
{
    if(pre.lenght==0||vin.length==0) return null;

    let root=pre[0];        
    let vinRootIndex = vin.indexOf(root);
    let vinLeft=vin.slice(0,vinRootIndex);
    let vinRight=vin.slice(vinRootIndex+1);
        
    let preLeft=pre.slice(1,vinLeft.length+1);
    let preRight=pre.slice(vinLeft.length+1);
        
    let node={
        val:root,
        left:reConstructBinaryTree(preLeft,vinLeft),
        right:reConstructBinaryTree(preRight,vinRight)
     };
     return node;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

// 返回的结果
1. *{val: 1, left: {…}, right: {…}}*

2. 1. left:

   2. 1. left:

      2. 1. left: null

         2. right:

         3. 1. left: null
            2. right: null
            3. val: 7
            4. __proto__: Object

         4. val: 4

         5. __proto__: Object

      3. right: null

      4. val: 2

      5. __proto__: Object

   3. right:

   4. 1. left: {val: 5, left: null, right: null}
      2. right: {val: 6, left: {…}, right: null}
      3. val: 3
      4. __proto__: Object

   5. val: 1

   6. __proto__: Object

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

# 1.12 leetcode-637-二叉树的层平均值

给定一个非空二叉树, 返回一个由每层节点平均值组成的数组。

输入：
    3
   / \
  9  20
    /  \
   15   7
输出：[3, 14.5, 11]

1
2
3
4
5
6
7

显而易见，此题用到的是BFS。

let node = { val: 3, left: { val: 9, left: null, right: null }, right: { val: 20, left: { val: 15, left: null, right: null }, right: { val: 7, left: null, right: null } } };
    var averageOfLevels = function (root) {
      let res = [];
      if (!root) return res;
      res = [root.val];
      let queue = [root];
      while (queue.length) {
        let num = 0;
        let nextLevel = [];
          
        queue.forEach(item => {
          if (item.left) {
            nextLevel.push(item.left);
            num += item.left.val;
          }
          if (item.right) {
            nextLevel.push(item.right);
            num += item.right.val;
          }
        })

        nextLevel.length && res.push(num / nextLevel.length)

        queue = nextLevel;
      }
      return res;
    };

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

# 二、多叉树

数据结构

[{key: a, children: [{key: b, children: null}]},{key: c, children: null}]

# 2.1 相关计算

# 2.1.1 获取子树

function getChildTree(data, key) {
      return getChidTreeFn(data);

      function getChidTreeFn(data) {
        if (data) {
          if (Array.isArray(data)) {
            let res = null;
            for (let item of data) {
              res = getChidTreeFn(item);
              if (res) break;
            }
            return res;
          } else if (data.key === key) {
            return data;
          } else return getChidTreeFn(data.children);
        }
      }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

# 2.1.2 获取父级key

function getParent(data, key) {
  if (typeof data === "object" && data) {
    let val = Array.isArray(data) ? [] : {};
    for (let i in data) {
      val[i] = getParent(data[i], key);
      if (i === "children" && val[i]) {
        console.log('children', val[i])
        val[i].forEach(item => {
          console.log('111', item, item.key, key, item.key === key)
          if (item.key === key) {
            console.log('父元素', val.key);
          }
        });
      }
    }
    return val
  } else {
    return data
  }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

# 2.1.3 获取叶子结点

function getAllLeaf(data) {
    let result = [];

    function getLeaf(data) {
        if (Array.isArray(data)) {
            data.forEach(item => {
                if (!item.children) {
                    result.push(item.key);
                } else {
                    getLeaf(item.children);
                }
            });
        } else {
            if (!data.children) {
                result.push(data.key);
            } else {
                getLeaf(data.children);
            }
        }
    }
    getLeaf(data);
    return result;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

# 2.1.4 获取根结点到叶子结点的路径

方法一：如果是叶子结点，就更新路径，并存起来；如果不是则只更新路径，继续遍历。

function getAllPath(data) {
    let paths = []
    getAllPathFn(data)
    return paths

    function getAllPathFn(data, path = []) {
        data.forEach(i => {
            if (!i.children) {
                path.push(i.key)
                paths.push(path)
            } else {
                let tmp = JSON.parse(JSON.stringify(path))
                tmp.push(i.key)
                getAllPathFn(i.children, tmp)
            }
        })
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

方法二：

function fn(list){
    let path=''
    let oldPath=''
    let result={}
    function handle(data,_path){
        for(let item of data){
            result[item.key]=_path?_path+'-'+item.key:_path+item.key
            if(item.children){
                handle(item.children,result[item.key])
            } 
        }
    }
    handle(list,path)
    return result
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

编程小技巧浏览器

LinHuijuan's Blog

Choose mode

树

# 树

# 一、二叉树

# 1.1 leetcode-100-相同的树

# 1.2 leetcode-101-对称二叉树

# 1.3 leetcode-104-二叉树的最大深度

# 1.4 leetcode-107-二叉树的层次遍历II

# 1.5 leetcode-110-平衡二叉树

# 1.6 leetcode-111-二叉树的最小深度

# 1.7 leetcode-112-路径总和

# 1.8 leetcode-226-翻转二叉树

# 1.9 leetcode-235-二叉搜索树的最近公共祖先

# 1.10 leetcode-257-二叉树的所有路径

# 1.11 重建二叉树

# 1.12 leetcode-637-二叉树的层平均值

# 二、多叉树

# 2.1 相关计算

# 2.1.1 获取子树

# 2.1.2 获取父级key

# 2.1.3 获取叶子结点

# 2.1.4 获取根结点到叶子结点的路径