遍历二叉树，然后找出二叉树每行最大值

js 是没有二叉树这个数据结构的，所以写出的答案只能提交在 letcode 上面。

二叉树在我看来，可以把它理解为一个对象，并且拥有以下属性：val，left，right。

用一张图来表示：

未命名文件.jpg

如何遍历二叉树呢？我的记忆告诉我，需要使用到递归的方法。

为了好理解，我先出一个简单的题目吧。

帮助理解的例子

请遍历一个二叉树的所有节点，并打印出该节点的 val。

解析：

1 递归是一个函数会不断循环调用自己，但是会有一个判断条件来终止循环。

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 {string[]}
 */
var binaryTreePaths = function(root) {
    function helper(root) {
        if(root) {
            console.log(root.val)
            helper(root.left)
            helper(root.right)
        }
    }
    helper(root)
};

打印顺序应该为（无法在控制台中演示）

遍历出二叉树的所有路径

来看看 leetcode 上的一道题目 https://leetcode.cn/problems/binary-tree-paths/ 。

给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。

叶子节点 是指没有子节点的节点。

示例 1：

输入： root = [1,2,3,null,5]
输出： ["1->2->5","1->3"]

示例 2：

输入： root = [1]
输出： ["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 {string[]}
 */
var binaryTreePaths = function(root) {
    const res = []
    function helper(root, path) {
        // 当前节点存在（不管他的 left 或者 right 值是否存在）
        if(root) {
            path += root.val
            if(root.left || root.right) {
                // 如果存在 left 或 right 才加上 '->'
                path += '->'
                helper(root.left, path)
                helper(root.right, path)
            } else {
                res.push(path)
            }
        }
    }
    helper(root, "")
    return res
};

找出二叉树每行最大值

https://leetcode.cn/problems/find-largest-value-in-each-tree-row/description/

方案 1

height 可以理解为二叉树的行索引。

直接判断 res 数组在当前行的位置有没有值。有值就判断取最大值，没值就把当前的 val push 到该位置。

/**
 * 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 largestValues = function(root) {
    const res = []
    function helper(root, height) {
        if(root) {
            // 在这里 height 相当于 res 的索引。判断 res[height] 是否存在值。
            // 不过这里会有个问题，res[height] = 0 会判断为没有值，
            // 所以要把这个条件单独拿出来判断
            if(res[height] || res[height] === 0) {
                res[height] = Math.max(res[height], root.val)
            } else {
                res[height] = root.val
            }

            if(root.left || root.right) {
                helper(root.left, height + 1)
                helper(root.right, height + 1)
            }

        }
    }
    helper(root, 0)
    return res
};

方案 2

通过 res.length 和二叉树行索引来判断 res 代表的当前行的值是否存在。

function largestValues(root: any) {
  const res = [] as any[]
  // 每个递归函数都通过参数访问到 res
  // 其实这里 res 是引用数据类型，不通过参数传递，放在最外层作用域也可以。
  function dfs(root: any, res: any[], height: number) {
    if(!root) {
      return
    }
    // 在 res 还没 push root.val 之前，res.length === height
    if(res.length === height) {
      res.push(root.val)
    } else {
      res.splice(height, 1, Math.max(res[height], root.val))
    }

    if(root.left) {
      dfs(root.left, res, height + 1)
    }
    if(root.right) {
      dfs(root.right, res, height + 1)
    }
  }
  dfs(root, res, 0)
  return res
}

遍历二叉树，然后找出二叉树每行最大值 ​

帮助理解的例子 ​

遍历出二叉树的所有路径 ​

找出二叉树每行最大值 ​

方案 1 ​

方案 2 ​