美文网首页算法
二叉树的深度遍历和反转

二叉树的深度遍历和反转

作者: mapleLeaf_X | 来源:发表于2020-03-11 09:54 被阅读0次

    基本概念

    二叉树的每个节点最多只有两颗字树,左子树和右子树,次序不能颠倒。
    ==== 性质 ====
    非空的二叉树的第n层最多有2^(n-1)个元素;
    深度为h的二叉树最多有2^h-1个节点。

    ==== 满二叉树 ====
    满二叉树除了最后一层的节点,其他节点都有两个子节点。
    若满二叉树的深度为h,那么这棵树的节点数必然是2^h-1.

    二叉树的遍历

    遍历即将树的所有结点访问且仅访问一次。按照根节点位置的不同分为前序遍历,中序遍历,后序遍历。

    前序遍历:根节点->左子树->右子树
    
    中序遍历:左子树->根节点->右子树
    
    后序遍历:左子树->右子树->根节点
    

    例如:求下面树的三种遍历

    二叉树图gif.gif
    前序遍历:abdefgc
    
    中序遍历:debgfac
    
    后序遍历:edgfbca
    

    算法求解二叉树的深度

    给定一个二叉树,求二叉树的深度。
    首先进行分析,要求出二叉树的深度,那么我们必须要对二叉树进行遍历,对每个节点都需要去走一遍。
    要求对树进行遍历,那么我们肯定会选择一种遍历的方法,由于是从根节点开始的,于是我选取的是前序遍历。
    根据上边二叉树的前序遍历来进行深度的求解,当树节点没有了子树节点后返回0,每回到上一层次就+1,到达根节点的时候就判断左右子树所返回的值取大的那个,就是我们所求的最大深度。

    二叉树正向.PNG

    如 上图的深度为5.

    下面就是js代码的实现方式。

    /**
     * Definition for a binary tree node.
     * function TreeNode(val) {
     *     this.val = val;
     *     this.left = this.right = null;
     * }
     */
    /**
     * @param {TreeNode} root
     * @return {number}
     */
    var maxDepth = function(root) {
    
        // 第一种方法,因为将root树当成值传入到了TreeNode里边,所以在后边出现了list.val.letf的地方。
        let list = new TreeNode(root);
        let height,left,right;
        
        if(list.val === null){
            return 0;
        }
        
        left = maxDepth(list.val.left);
        right = maxDepth(list.val.right);
        height = (left>right?left:right)+1;
        
        return height;
    
        // 第二种方法,直接上手
        return root === null ? 0 : Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    };
    

    算法求解二叉树的反转

    得到题目,首先要判断一下,所给的树是不是空的,如果为空,那么就不需要去计算了。
    其次,从根节点开始遍历,知道找到最下层的树节点,然后将左右节点的值进行交换,一步一步向上层走,知道根节点的左右子树交换完。
    其实,这个题和上边求解二叉树的深度的题是相差不大的,只是将深度的计算变成了两个值的交换。

    二叉树反转.PNG

    二叉树的反转如上图。

    下边是二叉树反转的代码。

    /**
     * Definition for a binary tree node.
     * function TreeNode(val) {
     *     this.val = val;
     *     this.left = this.right = null;
     * }
     */
    /**
     * @param {TreeNode} root
     * @return {TreeNode}
     */
    var invertTree = function(root) {
        if (!root)
            return null;
            
        // recursive
        invertTree(root.left);
        invertTree(root.right);
        temp = root.left;
        root.left = root.right;
        root.right = temp;
        
        return root;
    };
    

    总结

    二叉树的遍历很简单,但是出的题会非常的多,比如,求取节点的个数,比较两颗树是否相等等等。学无止境,不断前进。

    相关文章

      网友评论

        本文标题:二叉树的深度遍历和反转

        本文链接:https://www.haomeiwen.com/subject/hrhanftx.html