實戰LeetCode - 前端面試必備二叉樹算法

本文概要1. 二叉樹簡介

二叉樹是一種非常重要的數據結構，很多其它數據結構都是基於二叉樹的基礎演變而來的。對於二叉樹，有深度遍歷和廣度遍歷，深度遍歷有前序、中序以及後序三種遍歷方法，廣度遍歷即我們平常所說的層次遍歷。因為樹的定義本身就是遞歸定義，因此採用遞歸的方法去實現樹的三種遍歷不僅容易理解而且代碼很簡潔，而對於廣度遍歷來說，需要其他數據結構的支撐，比如堆了。所以，對於一段代碼來說，可讀性有時候要比代碼本身的效率要重要的多。

2. 基礎二叉樹的構建

直接上代碼:

function Node(data, left, right) {
this.data = data;
this.left = left;
this.right = right;
}
Node.prototype.show = function () {
return this.data;
}

function BST() {
this.root = null;
}
BST.prototype.insert = function (data) {
var node = new Node(data, null, null);
if (this.root == null) {
this.root = node;
} else {
var current = this.root;
var parent;
while (true) {
parent = current;
if (data < current.data) {
current = current.left;
if (current == null) {
parent.left = node;
break;
}
} else {
current = current.right;
if (current == null) {
parent.right = node;
break;
}
}
}
}
}

var bst = new BST();
var nums = [10, 3, 18, 2, 4, 13, 21, 9, 8, 9];
for (var i = 0; i < nums.length; i++) {
bst.insert(nums[i]);
}

3.二叉樹前序遍歷

首先遍歷根節點，然後遍歷左子樹，最後遍歷右子樹

BST.prototype.perOrder = function (node) {
if (node) {
console.log(node.show() + " ");
this.perOrder(node.left);
this.perOrder(node.right);
}
}
bst.perOrder(bst.root);

4. 二叉樹中序遍歷

首先訪問左子樹，然後訪問根節點，字後訪問右子樹

BST.prototype.inOrder = function(node){
if(node){
this.inOrder(node.left);
console.log(node.show() + " ");
this.inOrder(node.right);
}
}
bst.inOrder(bst.root);

5. 二叉樹後序遍歷

BST.prototype.postOrder = function(node){
if(node){
this.postOrder(node.left);
this.postOrder(node.right);
console.log(node.show() + " ");
}
}
bst.postOrder(bst.root);

6. 查找二叉樹最小值

var minNode = function (node) {
if (node) {
while (node.left !== null) {
return minNode(node.left);
}
return node.data;
}
return null;
}

BST.prototype.findMin = function (root) {
return minNode(root)
}
bst.findMin(bst.root)

7. 查找二叉樹最大值

var maxNode = function (node) {
if (node) {
while (node.right !== null) {
return maxNode(node.right);
}
return node.key;
}
return null;
}
BST.prototype.findMax = function (root) {
return maxNode(root)
}
bst.findMax(bst.root)

8. 刪除二叉樹最小值

BST.prototype.delMinNode = function (root) {
if (!root) {
return false;
}
var current = root;
if (current.left == null) {
var rightNode = current.right;
return rightNode;
}
current.left = this.delMinNode(current.left);
return current;
}
bst.delMinNode(bst.root)

9. 刪除二叉樹最大值

BST.prototype.delMaxNode = function (root) {
if (!root) {
return false;
}
var current = root;
if (current.right == null) {
var leftNode = current.left;
return leftNode;
}
current.right = this.delMaxNode(current.right)
return current;
}
bst.delMaxNode(bst.root)

10. 判斷二叉樹是否存在某值

var searchNode = function (key, node) {
if (node == null) {
return false;
}
if (node.data > key) {
return searchNode(key, node.left);
} else if (node.data < key) {
return searchNode(key, node.right);
} else {
return true;
}
}
BST.prototype.search = function (key, root) {
return searchNode(key, root);
}
bst.search(3, bst.root)

11. 求二叉樹節點個數

BST.prototype.sizeOfTree = function (root) {
if (!root) {
return 0
}
return 1 + this.sizeOfTree(root.left) + this.sizeOfTree(root.right);
}
bst.sizeOfTree(bst.root)

12. 求二叉樹層級

BST.prototype.heightOfTree = function (root) {
if (!root) {
return 0
}
return Math.max(this.heightOfTree(root.left), this.heightOfTree(root.right)) + 1
}
bst.heightOfTree(bst.root)

13. 求二叉樹第K層的節點個數

BST.prototype.NumOfKthLevel = function (root, k) {
if (k < 0) {
return 0
}
if (root === null) {
return 0
}
if (root !== null && k === 1) {
return 1
}
return this.NumOfKthLevel(root.left, k - 1) + this.NumOfKthLevel(root.right, k - 1)
}
bst.NumOfKthLevel(bst.root,3)

14. 求二叉樹是否相同

BST.prototype.compareStruct = function (root1, root2) {
if (root1 === null && root2 === null) {
return true
}
if ((root1 !== null && root2 === null) || (root1 === null && root2 !== null)) {
return false
}
return (this.compareStruct(root1.left, root2.left) && this.compareStruct(root1.right, root2.right))
}
bst.compareStruct(bst.root, bst.root)

覺得本文對你有幫助？請分享給更多人
關注「React中文社區」加星標，每天進步