数据结构-二叉树-一一网

1. 二叉树的前中后遍历

中序遍历

 var inorderTraversal = function (root, array = []) {
     if(root){
         inorderTraversal(root.left, array);
         array.push(root);
         inorderTraversal(root.right, array);
     }
     return array;
 }
复制代码

前序遍历

    var preorderTraversal = function (root, array = []) {
      if (root) {
        array.push(root.val);
        preorderTraversal(root.left, array);
        preorderTraversal(root.right, array);
      }
      return array;
    };
复制代码

后序遍历

    var postorderTraversal = function (root, array = []) {
     if (root) {
       postorderTraversal(root.left, array);
       postorderTraversal(root.right, array);
       array.push(root.val);
     }
     return array;
   };
复制代码

2. 二叉树的镜像

操作给定的二叉树，将其变换为源二叉树的镜像。

比如：    源二叉树 
           8
          /  \
         6   10
        / \  / \
       5  7 9 11
       镜像二叉树
           8
          /  \
         10   6
        / \  / \
       11 9 7  5
复制代码

/**
* Definition for a binary tree node.
* function TreeNode(val) {
*     this.val = val;
*     this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {void}
*/
var mirror = function(root) {
   if (!root) return ;
   mirror(root.left);
   mirror(root.right);
   let tmp = root.left;
   root.left = root.right;
   root.right = tmp;
   
};
复制代码

递归写法即可

3. 二叉树的深度

输入一棵二叉树的根结点，求该树的深度。

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var treeDepth= function(root) {
    if(!root) return 0;
    return Math.max(treeDepth(root.left), treeDepth(root.right)) + 1;
};
复制代码

4. 平衡二叉树

输入一棵二叉树的根结点，判断该树是不是平衡二叉树。

如果某二叉树中任意结点的左右子树的深度相差不超过 1，那么它就是一棵平衡二叉树。

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isBalanced = function(root) {
    
    let ans = true;
    dfs(root);
    
    function dfs(root) {
        if(!root) return 0;
        let left = dfs(root.left), right = dfs(root.right);
        if(Math.abs(left-right) > 1) ans = false;
        return Math.max(left, right) + 1;
    }    
    
    return ans;
};
复制代码