二叉树的深度遍历和反转

基本概念

二叉树的每个节点最多只有两颗字树，左子树和右子树，次序不能颠倒。
==== 性质 ====
非空的二叉树的第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;
};

总结

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