乐趣区

关于javascript:二叉树反转

递归

自顶向下

// 先替换顶层节点,再替换底层节点
var invertTree = function(root) {if(root === null) return null;
    // 替换左右结点
    var tmp = root.left;
    root.left = root.right;
    root.right = tmp;
    if(root.left){invertTree(root.left);
    }
    if(root.right){invertTree(root.right);
    }
    return root;
};

自底向上

// 先替换底层节点,再替换顶层节点
var invertTree = function(root) {
    // 定义递归返回的条件
    if(!root)   return null;
    // 先应用递归找到最底层的左右子树
    let left = invertTree(root.left);
    let right = invertTree(root.right);
    // 别离替换左右子树
    root.right = left;
    root.left = right;
    return root;
}

迭代

思路:保护一个数组,这个数组外面寄存的是没有替换过左右子树的节点

// 思路:保护一个数组,这个数组外面寄存的是没有替换过左右子树的节点
// 自顶向下
var invertTree = function(root) {if(!root)   return null;
    // 这个数组一开始寄存的只有根结点
    var arr = [root];
    while(arr.length) {let current = arr.pop();
        // 别离替换 current 节点的左右子树
        let temp = current.left;
        current.left = current.right;
        current.right = temp;

        // 再判断 current 节点的左右子树是否存在,如果存在则放进数组
        if(current.left)    arr.push(current.left);
        if(current.right)   arr.push(current.right);
    }
    return root;
}
退出移动版