my canteen
登录       注册

您现在的位置是:网站首页 > 学无止境

LeetCode(3)-先序遍历

王伟2020年9月4日61人围观
简介LeetCode(3)-先序遍历

LeetCode(3)-先序遍历

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

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

示例:
输入:
   1
 /   \
2     3
 \
  5
输出: ["1->2->5", "1->3"]
解释: 所有根节点到叶子节点的路径为: 1->2->5, 1->3

在对搜索二叉树的封装时 已经对先序遍历实现进行编写,值得注意的是我们在弹出res数组时要撤销最末尾的选择,我们不容易注意到其实在之中隐藏着回溯

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {string[]}
 */
var binaryTreePaths = function(root) {
    const res = []
    let strPath = ''
   if(root==null){
       return []
   }
    const preOrderTraverse = (root,strPath)=>{
        if(root.left==null&&root.right==null){
            strPath += root.val //叶子节点
            res.push(strPath)
            return
        }
        strPath += root.val+'->'
        if(root.left){
            preOrderTraverse(root.left,strPath)
        }
        if(root.right){
            preOrderTraverse(root.right,strPath)//注意传入的第二个参数 暗含回溯
        }
    }
    preOrderTraverse(root,strPath)
    return res
};

在LeetCode中笨猪爆破组的分享也让我更好的理解了前中后序遍历

如果有人问你,前中后序遍历的区别是什么?他可能不希望你回答根左右之类,他希望你抓住实质,他会继续问你为什么。

  • 1.而且如果你回答:中序遍历是先访问左子树,再访问根节点……就很不OK。
  • 2.中序遍历也是先访问根节点,再左子树,再右子树,只是将 do something with root 放在了访问完左子树之后,或者说:access the data part of the current root.
  • 3.因为 DFS 遍历,每个节点是有 3 次不同的驻留阶段的,在其中一个时间点 do something with root,就分别对应前中后遍历。

唯一的区别是:

  • 1.在遍历期间,他们将在什么时候访问一个节点的内容-
  • 2.因为对于二叉树,一个节点实际上被访问了3次。
  • 3.它们包括:第一次DFS调用之前的时间,以及每次DFS调用之后的时间

1.前序遍历在第一次访问节点时(在其左子节点的DFS之前)访问该节点的内容。具体实施如下:

Preorder (root) {
    access content of root 
    Call Preorder(root.left)
    Call Preorder(root.right)
 }

2.后序遍历在最后一次访问节点时(在两个子节点上的DFS之后)访问该节点的内容。具体实施如下:

Postorder (root) {
   Call Postorder(root.left)
   Call Postorder(root.right)
   access content of root
}

3.中序遍历在访问右子节点之前,inorder遍历访问节点的内容。具体实施如下:

Inorder (root) {
    Call Inorder(root.left) 
    access content of root
    Call Inorder(root.right)
 }

路漫漫其修远兮,吾将上下而求索


文章评论

  • 帅哥 2020年9月4日 21:58

    好好好

来说句话吧.... 共有评论数:1条


微信二维码 博主微信 qq二维码 博主QQ
177****8743
7*24小时电话