树—leetcode - 《算法》

104 二叉树的最大深度
111 二叉树的最小深度
102 二叉树的层序遍历
94 二叉树中的中序遍历
- 递归版：
- 非递归版：
112 路径总和
前端与树-遍历JSON的所有节点值
前端与树-渲染antd的树组件

104 二叉树的最大深度

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

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

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

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

返回它的最大深度 3 。

解题思路：

求最大深度，考虑使用深度优先遍历
在深度优先遍历过程中，记录每个节点所在的层级，找出最大的层级即可。

解题步骤：

新建一个遍量，记录最大深度。
深度优先遍历整棵树，并记录每个节点的层级，同时不断刷新最大深度这个变量。

遍历结束返回最大深度这个变量。

var maxDepth = function(root) {
  let res = 0;
  const dfs = (n, level) => {
      if(!n) { return ;};
      console.log(n.val);
      if(!res.left && !res.right) {
          res = Math.max(res, level)
      };
      dfs(n.left, level+1);
      dfs(n.right, level+1);
  }
  dfs(root, 1);
  return res;
};

111 二叉树的最小深度

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

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

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

示例:

给定二叉树 [3,9,20,null,null,15,7],

3<br />   / \<br />  9  20<br />    /  \<br />   15   7<br />返回它的最小深度  2.

解题思路：

求最小深度，考虑使用广度优先遍历。
在广度优先遍历过程中，遇到叶子节点，停止遍历，返回节点层级

解题步骤：

广度优先遍历整棵树，并记录每个节点的层级。

遇到叶子节点，返回节点层级，停止遍历。

var minDepth = function(root) {
  if(!root) {return 0};
  const q = [[root, 1]];
  while(q.length) {
      const [n, level] = q.shift();
      console.log(n.val, level);
      if(!n.left && !n.right) {
          return level
      }
      if(n.left) q.push([n.left, level+1]);
      if(n.right) q.push([n.right, level+1]);
  }
};

102 二叉树的层序遍历

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

3<br />   / \<br />  9  20<br />    /  \<br />   15   7<br />返回其层次遍历结果：

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

解题思路：

层序遍历顺序就是广度优先遍历
不过在遍历时候需要记录当前节点所处的层级，方便将其添加到不同的数组中。

解题步骤：

广度优先遍历二叉树。

遍历过程中，记录每个节点的层级，并将其添加到不同的数组中。

var levelOrder = function(root) {
  if(!root) { return []};
  const q = [[root, 0]];
  const res = [];
  while(q.length) {
     const [n,level] = q.shift();

     if(!res[level]) {
         res.push([n.val]);
     }else {
         res[level].push(n.val)
     }
     if(n.left) q.push([n.left, level+1]);
      if(n.right) q.push([n.right, level+1]);
  }

  return res;
};

方法2：

var levelOrder = function(root) {
    if(!root) { return []};
    const q = [root];
    const res = [];
    while(q.length) {
        let len = q.length;
        res.push([])
        while(len--) {
            const n = q.shift();

            res[res.length-1].push(n.val);
            if(n.left) q.push(n.left);
            if(n.right) q.push(n.right);
        }
    }

    return res;
};

94 二叉树中的中序遍历

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

示例:

输入: [1,null,2,3]
1
\
2
/
3

输出: [1,3,2]

递归版：

var inorderTraversal = function(root) {
    const res = [];
    const rec = (n)=>{
        if(!n) return [];
        rec(n.left);
        res.push(n.val);
        rec(n.right); 
    }
    rec(root)
    return res;
};

非递归版：

var inorderTraversal = function(root) {
    const res = [];
    const stack = [];
    let p = root;
    while(stack.length || p) {
        while(p) {
            stack.push(p);
            p = p.left;
        }

        const n = stack.pop()
        res.push(n.val)
        p = n.right
    }
    return res;
};

112 路径总和

示例:
给定如下二叉树，以及目标和 sum = 22，

          5<br />             / \<br />            4   8<br />           /   / \<br />          11  13  4<br />         /  \      \<br />        7    2      1<br />返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。

解题思路：

在深度优先遍历过程中，记录当前路径的节点值的和。
在叶子节点处，判断当前路径的节点值的和是否等于目标值。

解题步骤：

深度优先遍历二叉树，在叶子节点处，判断当前路径的节点值的和是否等于目标值，是就返回true。

遍历结束，如果没有匹配，就返回false。

var hasPathSum = function(root, sum) {
  if(!root) return false;
  let res = false;
  const dfs = (n, s) => {

      if(!n.left && !n.right && s === sum) {
          res = true;
      }
      if(n.left) dfs(n.left, s + n.left.val);
      if(n.right) dfs(n.right, s + n.right.val)
  }

  dfs(root, root.val);
  return res;
};

前端与树-遍历JSON的所有节点值

const json = {
    a: {b: {c: 1}},
    d: [1, 2]
};

const a = Object.keys([1,2])

const dfs = (n, path) => {
    console.log(n, path);
    Object.keys(n).forEach(k=>{
        dfs(n[k], path.concat(k))
    })
}

dfs(json, [])

前端与树-渲染antd的树组件

import React, {FunctionComponent } from 'react';
import { Tree } from "antd";
const {  TreeNode } = Tree;
interface ITreeData {
    title: string;
    key: string;
    children?:Array<ITreeData>
}
const treeData:Array<ITreeData> = [
    {
      title: 'parent 1',
      key: '0-0',

      children: [
        {
          title: 'parent 1-0',
          key: '0-0-0',
          children: [
            { title: 'leaf', key: '0-0-0-0' },
            { title: 'leaf', key: '0-0-0-1' },
            { title: 'leaf', key: '0-0-0-2'},
          ],
        },
        {
          title: 'parent 1-1',
          key: '0-0-1',
          children: [{ title: 'leaf', key: '0-0-1-0' }],
        },
        {
          title: 'parent 1-2',
          key: '0-0-2',
          children: [
            { title: 'leaf', key: '0-0-2-0' },
            {
              title: 'leaf',
              key: '0-0-2-1',
            },
          ],
        },
      ],
    },
    {
      title: 'parent 2',
      key: '0-1',
      children: [
        {
          title: 'parent 2-0',
          key: '0-1-0',
          children: [
            { title: 'leaf', key: '0-1-0-0',children: [
                { title: 'leaf', key: '0-1-0-4'},
                { title: 'leaf', key: '0-1-0-2'},
              ]},
            { title: 'leaf', key: '0-1-0-1'},
          ],
        },
      ]
    },
  ];



export const TreeComponent: FunctionComponent = () => {
    const dfs = (n:ITreeData) => {
        return(
            <TreeNode title={n.title} key={n.key}>
                {n?.children?.map(dfs)}
            </TreeNode>
        )
    }
    return (
        <Tree>
           {treeData.map(dfs)}
        </Tree>
    );
};