深度优先搜索，后序遍历，递归 + 迭代和哈希表，2 解法求解《687. 最长同值路径》

代码数据结构:树数据结构:二叉树数据结构:哈希表算法:递归算法:迭代查找:深度优先搜索遍历:后序遍历语言:JavaScript语言:Go语言:PHP语言:Python语言:C语言:C++语言:C#语言:TypeScript语言:Java
2022-09-02 18:59:44
深度优先搜索，后序遍历，递归 + 迭代和哈希表，2 解法求解《687. 最长同值路径》

例题

687. 最长同值路径

给定一个二叉树的 root ，返回 最长的路径的长度 ，这个路径中的 每个节点具有相同值 。 这条路径可以经过也可以不经过根节点。
两个节点之间的路径长度 由它们之间的边数表示。
示例 1:
《687. 最长同值路径》示例 1 二叉树 [5，4，5，1，1，5]
输入：root = [5,4,5,1,1,5]
输出：2
示例 2:
《687. 最长同值路径》示例 2 二叉树 [1，4，5，4，4，5]
输入：root = [1,4,5,4,4,5]
输出：2
提示:
树的节点数的范围是 [0, 104]
-1000 <= Node.val <= 1000
树的深度将不超过 1000

答案

深度优先搜索 · 后序遍历 · 递归

var longestUnivaluePath = function(root) {
  let r = 0
  ;(function d(n, p) {
    if (n === null) return 0
    const t1 = d(n.left, n), t2 = d(n.right, n)
    r = Math.max(r, t1 + t2)
    return p && p.val === n.val ? Math.max(t1, t2) + 1 : 0 
  })(root, null)
  return r
};
var longestUnivaluePath = function(root) {
  let ans = 0
  ;(function d(n){
    if (n === null) return 0
    let l = d(n.left), r = d(n.right)
    l = n.left?.val === n.val ? l + 1 : 0
    r = n.right?.val === n.val ? r + 1 : 0
    ans = Math.max(ans, l + r)
    return Math.max(l, r)
  })(root)
  return ans
};
function longestUnivaluePath(root: TreeNode | null): number {
  let ans = 0
  const d = n => {
    if (n === null) return 0
    let l = d(n.left), r = d(n.right)
    l = n.left?.val === n.val ? l + 1 : 0
    r = n.right?.val === n.val ? r + 1 : 0
    ans = Math.max(ans, l + r)
    return Math.max(l, r)
  }
  return d(root), ans
};
class Solution {
  private $ans = 0;
  function d($n) {
    if ($n === null) return 0;
    $l = $this->d($n->left);
    $r = $this->d($n->right);
    $l = $n->left && $n->left->val === $n->val ? $l + 1 : 0;
    $r = $n->right && $n->right->val === $n->val ? $r + 1 : 0;
    $this->ans = max($this->ans, $l + $r);
    return max($l, $r);
  }
  function longestUnivaluePath($root) {
    $this->d($root);
    return $this->ans;
  }
}
func longestUnivaluePath(root *TreeNode) int {
  ans := 0
  var d func(n *TreeNode) int
  d = func(n *TreeNode) int {
    if n == nil {
      return 0
    }
    l, r := d(n.Left), d(n.Right)
    if n.Left != nil && n.Left.Val == n.Val {
      l++
    } else {
      l = 0
    }
    if n.Right != nil && n.Right.Val == n.Val {
      r++
    } else {
      r = 0
    }
    ans = max(ans, l + r)
    return max(l, r)
  }
  d(root)
  return ans
}
func max(a, b int) int {
  if a > b {
    return a
  }
  return b
}
class Solution {
  private int ans = 0;
  public int d(TreeNode n) {
    if (n == null) return 0;
    int l = d(n.left), r = d(n.right);
    l = n.left != null && n.left.val == n.val ? l + 1 : 0;
    r = n.right != null && n.right.val == n.val ? r + 1 : 0;
    ans = Math.max(ans, l + r);
    return Math.max(l, r);
  }
  public int longestUnivaluePath(TreeNode root) {
    d(root);
    return ans;
  }
}
public class Solution {
  private int ans = 0;
  private int d(TreeNode n) {
    if (n == null) return 0;
    int l = d(n.left), r = d(n.right);
    l = n.left != null && n.left.val == n.val ? l + 1 : 0;
    r = n.right != null && n.right.val == n.val ? r + 1 : 0;
    ans = Math.Max(ans, l + r);
    return Math.Max(l, r);
  }
  public int LongestUnivaluePath(TreeNode root) {
    d(root);
    return ans;
  }
}
#define MAX(a, b) (a > b ? a : b)
int d(struct TreeNode* n, int* ans) {
  if (n == NULL) return 0;
  int l = d(n->left, ans), r = d(n->right, ans);
  l = n->left && n->left->val == n->val ? l + 1 : 0;
  r = n->right && n->right->val == n->val ? r + 1 : 0;
  *ans = MAX(*ans, l + r);
  return MAX(l, r);
}
int longestUnivaluePath(struct TreeNode* root){
  int ans = 0;
  d(root, &ans);
  return ans;
}
class Solution {
private:
  int ans = 0;
  int d(TreeNode* n) {
    if (n == nullptr) return 0;
    int l = d(n->left), r = d(n->right);
    l = n->left && n->left->val == n->val ? l + 1 : 0;
    r = n->right && n->right->val == n->val ? r + 1 : 0;
    ans = max(ans, l + r);
    return max(l, r);
  }
public:
  int longestUnivaluePath(TreeNode* root) {
    d(root);
    return ans;
  }
};
class Solution:
  def d(self, n: Optional[TreeNode]) -> int:
    if n == None: return 0
    l, r = self.d(n.left), self.d(n.right)
    l = l + 1 if n.left and n.left.val == n.val else 0
    r = r + 1 if n.right and n.right.val == n.val else 0
    self.ans = max(self.ans, l + r)
    return max(l, r)
  def longestUnivaluePath(self, root: Optional[TreeNode]) -> int:
    self.ans = 0
    self.d(root)
    return self.ans
class Solution:
  def longestUnivaluePath(self, root: Optional[TreeNode]) -> int: # nonlocal
    ans = 0
    def d(n: Optional[TreeNode]) -> int:
        if n == None: return 0
        l, r = d(n.left), d(n.right)
        l = l + 1 if n.left and n.left.val == n.val else 0
        r = r + 1 if n.right and n.right.val == n.val else 0
        nonlocal ans
        ans = max(ans, l + r)
        return max(l, r)
    d(root)
    return ans

深度优先搜索 · 后序遍历 · 迭代

var longestUnivaluePath = function(root) {
  let ans = 0, p = root, prev = null
  const stack = [], h = new Map
  while (stack.length || p) {
    while (p) {
      stack.push(p)
      p = p.left
    }
    const n = stack.pop()
    if (n.right === null || n.right === prev) {
      const l = n.left?.val === n.val ? h.get(n.left) + 1 : 0
      const r = n.right?.val === n.val ? h.get(n.right) + 1 : 0
      ans = Math.max(ans, l + r)
      h.set(n, Math.max(l, r))
      prev = n
    } else {
      stack.push(n)
      p = n.right
    }
  }
  return ans
};
function longestUnivaluePath(root: TreeNode | null): number {
  let ans = 0, p = root, prev = null
  const stack = [], h = new Map
  while (stack.length || p) {
    while (p) {
      stack.push(p)
      p = p.left
    }
    const n = stack.pop()
    if (n.right == null || n.right == prev) {
      const l = n.left?.val === n.val ? h.get(n.left) + 1 : 0
      const r = n.right?.val === n.val ? h.get(n.right) + 1 : 0
      ans = Math.max(ans, l + r)
      h.set(n, Math.max(l, r))
      prev = n
    } else {
      stack.push(n)
      p = n.right
    }
  }
  return ans
};
class Solution {
  function longestUnivaluePath($root) {
    $ans = 0;
    $stack = [];
    $p = $root;
    $prev = null;
    while (count($stack) || $p) {
      while ($p) {
        $stack []= $p;
        $p = $p->left;
      }
      $n = array_pop($stack);
      if ($n->right === null || $n->right === $prev) {
        $l = $n->left && $n->left->val === $n->val ? $n->left->p + 1 : 0;
        $r = $n->right && $n->right->val === $n->val ? $n->right->p + 1 : 0;
        $ans = max($ans, $l + $r);
        $n->p = max($l, $r);
        $prev = $n;
      } else {
        $stack []= $n;
        $p = $n->right;
      }
    }
    return $ans;
  }
}
func longestUnivaluePath(root *TreeNode) int {
  ans, stack, p, h := 0, []*TreeNode{}, root, map[*TreeNode]int{}
  var prev *TreeNode
  for len(stack) > 0 || p != nil {
    for p != nil {
      stack = append(stack, p)
      p = p.Left
    }
    n := stack[len(stack) - 1]
    stack = stack[:len(stack) - 1]
    if n.Right == nil || n.Right == prev {
      l, r := 0, 0
      if n.Left != nil && n.Left.Val == n.Val {
        l = h[n.Left] + 1
      }
      if n.Right != nil && n.Right.Val == n.Val {
        r = h[n.Right] + 1
      }
      ans = max(ans, l + r)
      h[n] = max(l, r)
      prev = n
    } else {
      stack = append(stack, n)
      p = n.Right
    }
  }
  return ans
}
func max(a, b int) int {
  if a > b {
    return a
  }
  return b
}
class Solution {
  public int longestUnivaluePath(TreeNode root) {
    int ans = 0;
    Deque<TreeNode> stack = new ArrayDeque<TreeNode>();
    TreeNode p = root, prev = null;
    Map<TreeNode, Integer> h = new HashMap<TreeNode, Integer>();
    while (stack.isEmpty() == false || p != null) {
      while (p != null) {
        stack.push(p);
        p = p.left;
      }
      TreeNode n = stack.pop();
      if (n.right == null || n.right == prev) {
        int l = n.left != null && n.left.val == n.val ? h.get(n.left) + 1 : 0;
        int r = n.right != null && n.right.val == n.val ? h.get(n.right) + 1 : 0;
        ans = Math.max(ans, l + r);
        h.put(n, Math.max(l, r));
        prev = n;
      } else {
        stack.push(n);
        p = n.right;
      }
    } 
    return ans;
  }
}
public class Solution {
  public int LongestUnivaluePath(TreeNode root) {
    int ans = 0;
    Stack<TreeNode> stack = new Stack<TreeNode>();
    TreeNode p = root, prev = null;
    Dictionary<TreeNode, int> h = new Dictionary<TreeNode, int>();
    while (stack.Count > 0 || p != null) {
      while (p != null) {
        stack.Push(p);
        p = p.left;
      }
      TreeNode n = stack.Pop();
      if (n.right == null || n.right == prev) {
        int l = n.left != null && n.left.val == n.val ? h[n.left] + 1 : 0;
        int r = n.right != null && n.right.val == n.val ? h[n.right] + 1 : 0;
        ans = Math.Max(ans, l + r);
        h.Add(n, Math.Max(l, r));
        prev = n;
      } else {
        stack.Push(n);
        p = n.right;
      }
    }
    return ans;
  }
}
#define MAX(a, b) (a > b ? a : b)
typedef struct {
  struct TreeNode* key;
  int val;
  UT_hash_handle hh;
} HashItem;
int longestUnivaluePath(struct TreeNode* root){ // uthash 实现
  int ans = 0, pos = 0;
  struct TreeNode** stack = malloc(sizeof(struct TreeNode*) * 1e4);
  struct TreeNode* p = root;
  struct TreeNode* prev = NULL;
  HashItem* h = NULL;
  while (pos > 0 || p) {
    while (p) {
      stack[pos++] = p;
      p = p->left;
    }
    struct TreeNode* n = stack[--pos];
    if (n->right == NULL || n->right == prev) {
      int l = 0, r = 0;
      if (n->left && n->left->val == n->val) {
        HashItem* pEntry = NULL;
        HASH_FIND_INT(h, &n->left, pEntry);
        if (pEntry) l = pEntry->val + 1;
      } 
      if (n->right && n->right->val == n->val) {
        HashItem* pEntry = NULL;
        HASH_FIND_INT(h, &n->right, pEntry);
        if (pEntry) r = pEntry->val + 1;
      }
      ans = MAX(ans, l + r);
      HashItem* pEntry = malloc(sizeof(HashItem));
      pEntry->key = n;
      pEntry->val = MAX(l, r);
      HASH_ADD_INT(h, key, pEntry);
      prev = n;
    } else {
     stack[pos++] = n;
     p = n->right;
    }
  }
  return ans;
}
class Solution {
public:
  int longestUnivaluePath(TreeNode* root) {
    int ans = 0;
    stack<TreeNode*> st;
    TreeNode* p = root;
    TreeNode* prev = nullptr;
    unordered_map<TreeNode*, int> h;
    while (st.empty() == false || p) {
      while (p) {
        st.push(p);
        p = p->left;
      }
      TreeNode* n = st.top();
      st.pop();
      if (n->right == nullptr || n->right == prev) {
        int l = n->left && n->left->val == n->val ? h[n->left] + 1 : 0;
        int r = n->right && n->right->val == n->val ? h[n->right] + 1 : 0;
        ans = max(ans, l + r);
        h.emplace(n, max(l, r));
        prev = n;
      } else {
        st.push(n);
        p = n->right;
      }
    }
    return ans;
  }
};
class Solution:
  def longestUnivaluePath(self, root: Optional[TreeNode]) -> int:
    ans, stack, p, prev, h = 0, list(), root, None, dict()
    while len(stack) > 0 or p:
      while p:
        stack.append(p)
        p = p.left
      n = stack.pop()
      if n.right == None or n.right == prev:
        l = h[n.left] + 1 if n.left and n.left.val == n.val else 0
        r = h[n.right] + 1 if n.right and n.right.val == n.val else 0
        ans = max(ans, l + r)
        h[n] = max(l, r)
        prev = n
      else:
        stack.append(n)
        p = n.right
    return ans

相似例题

小宇
代码
二叉树的后序遍历：求监控二叉树和二叉树最大路径和
用二叉树的后序遍历，求解监控二叉树和二叉树的最大路径和
小宇
Github　力扣　M站　全部原创，请勿转载
定长列表，哈希映射两种数据结构，求解《1624. 两个相同字符之间的最长子字符串》
顺序遍历，定长列表，哈希映射两种数据结构，求解《1624. 两个相同字符之间的最长子字符串》
递归，迭代（定长列表 + 位集），3 解法求解《672. 灯泡开关 Ⅱ》
递归，迭代（定长列表 + 位集），3 解法求解《672. 灯泡开关 Ⅱ》
递归、迭代、前序遍历，3 解法，求解《669. 修剪二叉搜索树》
递归、迭代、前序遍历，3 解法，求解《669. 修剪二叉搜索树》