Sorry, your browser cannot access this site
This page requires browser support (enable) JavaScript
Learn more >

求两棵树的第一个交点

首先判断两棵树是否相交,可以根据判断两个链表是否相交扩展而来,如果相交的话,将第1个链表的末尾指向第1个链表的头部将会成环,因此借鉴这种思路

自己的思路如下:KlYSSU

验证两棵树是否相交

思路:Morris先序遍历,遍历第1棵树的时候将叶节点的左指针指向root1,然后遍历root2,如果发现某一个节点左指针指向第1个树根,说明相交,包含了两个树中有一个是子树的情况

时间复杂度:O(N)
空间复杂度:O(1)

Morris遍历:

优点:不同于我们之前递归遍历或者借助栈来进行树的遍历,因为Morris遍历可以在保证时间复杂度依然为O(N)的情况下可以将空间复杂度降低为O(1)

假设当前节点为cur,最一开始来到树根,什么时候停呢,当cur来到nil的时候就停止

  1. 如果当前节点没有左子树,直接向右移动
  2. 如果当前节点有左子树,找到当前节点左子树的最右节点mostRight
    1. 如果mostRight的右指针指向null,那么mostRight.Right=Cur,cur=cur.Left
    2. 如果mostRight的右指针指向cur,那么mostRight.Right=nil,cur=cur.Right

遍历之后发现一个问题:任何一个节点,只要有左孩子Morris遍历的时候会遍历两次,也就是有左树的节点,左树不为空,首先遍历当前节点,然后遍历左树,遍历之后再回到当前节点,所以当前节点会遍历两次。因为用这个就可以知道是第一次来到自己还是第二次来到自己。

Morris先序遍历:

第一次遍历到该节点的时候直接打印(没有左子树的节点会遍历到一次,有左子树的节点会遍历到两次,但是我们第一次就应该打印)

Morris先序遍历代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
func MorrisPreOrderTraverse(root *TreeNode) []int {
if root == nil {
return nil
}

var mostRight *TreeNode
cur := root
var ret []int
for cur != nil {
//如果当前节点没有左子树
if cur.Left == nil { //当前节点向右移动 (只有没有左子树的节点会走这一步)
ret = append(ret, cur.Val)
cur = cur.Right
} else { //找到当前节点左子树的最右节点
mostRight = cur.Left

for mostRight.Right != nil && mostRight.Right != cur {
mostRight = mostRight.Right
}
//此时mostRight就是当前节点左子树的最右节点
if mostRight.Right == nil { //说明是第一次来到
ret = append(ret, cur.Val)
mostRight.Right, cur = cur, cur.Left
} else { //说明是第二次来到(只有有左子树的时候才会有第二次来到)
mostRight.Right, cur = nil, cur.Right
}
}
}

return ret
}

二叉树树形结构,但是树中每个节点的分支最多只有两个,我们叫做二叉树 二叉搜索树(BST)!> 二叉搜索树又叫二叉排序树,或二叉查找树。它或者是一颗空树或者是具有下列性质的二叉树: 若它的左子树不为空,则左子树上的所有节点的值均小于它的根节点的值 若它的右子树不为空,则右子树上的所有节点的值均大于它的根节点的值 它的左右子树也分别是二叉排序树 平衡二叉树(AVL)!> 平衡二叉...

基于递归的遍历

步骤

  1. 以某个节点X为头结点的子树中,分析答案有哪些可能性,并且这种分析是以X的左子树,X的右子树,和X整棵树的角度来考虑可能性的
  2. 根据第一步分析的可能性,列出所需要的信息,例如在二叉树是否平衡中,左子树和右子树都需要知道各自是否平衡,以及高度这两个信息。
  3. 根据第二步信息汇总,定义自己的信息结构体
  4. 设计递归函数,递归函数是处理以X为头结点的情况相爱的答案,包括设计递归函数的base case,默认直接得到左树和右树所有的信息,以及把可能性左整合,并且返回第三步的信息结构这4个小步骤。