[binary tree] binary tree path finding

0x00 subject

On an infinite binary tree , Every node has Two Child node
Nodes in the tree Line by line Press... In turn “ And ” Mark with glyph
As shown in the figure below
stay Odd line （ namely , first line 、 The third line 、 The fifth row ……） in ,
Press From left to right In the order of
and Even number line （ namely , The second line 、 In the fourth row 、 Sixth elements ……） in ,
Press From right to left In the order of
Give you a tree node Label of label
Please return from root Node to this label by label The path of the node
The path is composed of passing node labels

Corn seed ：

 Input ：label = 14
 Output ：[1,3,4,14]

---

0x01 Ideas

Of each layer of a binary tree Number And Height relevant
The first 1 layer ,2 ^ 0 = 1, And take 1 start
The first 2 layer ,2 ^ 1 = 2, And take 2 start
The first 3 layer ,2 ^ 2 = 4, And take 4 start

When the binary tree is displayed in normal order

   1
  2,3
4,5,6,7

The relationship between the child node and the parent node is
p = c / 2

According to this rule
You can get from node To root On the path of All nodes
And then according to Number Get the name of the current node Height
And then to Need to reverse Layer of
according to Height You can find the middle of a layer
most Left edge L And the most Right edge R Value
There is also a current value C

How to find out C Symmetric value of V Well ？
Because after the reverse is symmetry Of
C Than L How much larger
V Just like R How much smaller
therefore
V = R - (C - L) = L + R - C

---

0x02 solution

Language ：Swift

Tree node ：TreeNode

public class TreeNode {
    public var val: Int
    public var left: TreeNode?
    public var right: TreeNode?
    public init() { self.val = 0; self.left = nil; self.right = nil; }
    public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
    public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
        self.val = val
        self.left = left
        self.right = right
    }
}

solution ：

func pathInZigZagTree(_ label: Int) -> [Int] {
    var res: [Int] = []
    
    //  Get all nodes on the path to the root 
    var val = label
    while val != 0 {
        res.append(val)
        val = val >> 1 //  Divide 2, It's equivalent to moving right 
    }
    
    //  In reverse order  [14,4,3,1] -> [1,3,4,14]
    res = Array(res.reversed())
    
    var count = res.count - 2
    while count > 0 {
        //  Left node value 
        let left = Int(pow(2.0, Float(count)))
        
        //  Right node value 
        let right = left + left - 1
        
        //  Current node value to be replaced 
        var val = res[count]
        
        //  Calculate the replacement value 
        val = left + right - val
        
        //  Replace 
        res[count] = val
        
        //  Upward , Skip a layer 
        count -= 2
    }
    return res
}

---

0x03 My work

Welcome to experience one of my works ： Small five pen small program -XWubi
Wubi learning is a good helper
WeChat Search ~

---