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 } } }
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 { //说明是第一次来到 mostRight.Right, cur = cur, cur.Left } else { //说明是第二次来到(只有有左子树的时候才会有第二次来到) ret = append(ret, cur.Val) mostRight.Right, cur = nil, cur.Right } } }
var mostRight *TreeNode cur := root var ret []int for cur != nil { if cur.Left == nil { cur = cur.Right } else { mostRight = cur.Left for mostRight.Right != nil && mostRight.Right != cur { mostRight = mostRight.Right } if mostRight.Right == nil { //说明是第一次遍历你到 mostRight.Right, cur = cur, cur.Left } else { mostRight.Right = nil //打印左子树的右边界 ret = append(ret, prinSubTreeRightEdge(cur.Left)...) cur = cur.Right } } }
//最后再打印一下整棵树的右边界即可 ret = append(ret, prinSubTreeRightEdge(root.Right)...) return ret }
funcprinSubTreeRightEdge(head *TreeNode) []int { if head == nil { returnnil }
var ret []int
//反转 var prev *TreeNode cur := head for cur != nil { prev, cur, cur.Right = cur, cur.Right, prev }
//此时prev指向反转之后的头 //开始打印 cur = prev for cur != nil { ret = append(ret, cur.Val) cur = cur.Right }
//反转回去 prev, cur = nil, prev for cur != nil { prev, cur, cur.Right = cur, cur.Right, prev }