基本概念
二叉树的每个节点最多只有两颗字树,左子树和右子树,次序不能颠倒。
==== 性质 ====
非空的二叉树的第n层最多有2^(n-1)个元素;
深度为h的二叉树最多有2^h-1个节点。
==== 满二叉树 ====
满二叉树除了最后一层的节点,其他节点都有两个子节点。
若满二叉树的深度为h,那么这棵树的节点数必然是2^h-1.
二叉树的遍历
遍历即将树的所有结点访问且仅访问一次。按照根节点位置的不同分为前序遍历,中序遍历,后序遍历。
前序遍历:根节点->左子树->右子树
中序遍历:左子树->根节点->右子树
后序遍历:左子树->右子树->根节点
例如:求下面树的三种遍历
二叉树图gif.gif前序遍历:abdefgc
中序遍历:debgfac
后序遍历:edgfbca
算法求解二叉树的深度
给定一个二叉树,求二叉树的深度。
首先进行分析,要求出二叉树的深度,那么我们必须要对二叉树进行遍历,对每个节点都需要去走一遍。
要求对树进行遍历,那么我们肯定会选择一种遍历的方法,由于是从根节点开始的,于是我选取的是前序遍历。
根据上边二叉树的前序遍历来进行深度的求解,当树节点没有了子树节点后返回0,每回到上一层次就+1,到达根节点的时候就判断左右子树所返回的值取大的那个,就是我们所求的最大深度。
如 上图的深度为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;
};
算法求解二叉树的反转
得到题目,首先要判断一下,所给的树是不是空的,如果为空,那么就不需要去计算了。
其次,从根节点开始遍历,知道找到最下层的树节点,然后将左右节点的值进行交换,一步一步向上层走,知道根节点的左右子树交换完。
其实,这个题和上边求解二叉树的深度的题是相差不大的,只是将深度的计算变成了两个值的交换。
二叉树的反转如上图。
下边是二叉树反转的代码。
/**
* 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;
};
总结
二叉树的遍历很简单,但是出的题会非常的多,比如,求取节点的个数,比较两颗树是否相等等等。学无止境,不断前进。
网友评论