当前位置：网站首页>[binary tree] the longest interleaved path in a binary tree

[binary tree] the longest interleaved path in a binary tree

2022-07-26 04:06:00 【How cold it is】

0x00 subject

Here's one for you root A binary tree for the root , The alternate paths in a binary tree are defined as follows ：

Select the binary tree arbitrarily Nodes and a direction （ Left perhaps Right ）
If the forward direction is Right , Then move to the current node Right Child node
Otherwise move to its Left Child node
Change the direction ： Left to right perhaps Right to left
Repeat steps 2 and 3 , Until you are in the tree unable Keep moving
The length of the interleaved path is defined as ：
Visited nodes number - 1（ The path length of a single node is 0 ）

Please return the longest of the given tree Alternate paths The length of

0x01 Ideas

use depth Priority traversal
Traverse Next When a child node
Yes, it can distinguish the node from Left node , still Right Node
By caching for each node 2 It's worth
A left value left, Indicates that this node is The left node when , Arrive at the required Number of paths
An R-value right, Indicates that this node is Right node when , Arrive at the required Number of paths
Because nodes are either Left node , Or Right node
So two values , One must be 0
Another one , According to this node is Left yes Right To make sure
yes Left node , The parent node's Right value + 1 (rihgt + 1)
yes Right node , The parent node's The left value + 1 (left + 1)
Finally, use one overall situation Variable
Save the maximum value

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 longestZigZag(_ root: TreeNode?) -> Int {
    var res: Int = 0
    
    func dfs(_ root: TreeNode?, _ left: Int, _ right: Int) {
        //  Maximum length 
        res = max(res, max(left, right))
        
        //  The left subtree exists , To the right 
        if let l = root?.left {
            dfs(l, right+1, 0)
        }
        
        //  Right subtree exists , To the left 
        if let r = root?.right {
            dfs(r, 0, left+1)
        }
    }
    
    dfs(root, 0, 0)
    return res
}