二叉树两个结点的最短路径

二叉树两个结点的最短路径

引用

CSDN

1.

https://blog.csdn.net/puspos/article/details/104659112

本文讨论了二叉树中两个节点的最短路径问题，包括两种情况：一个节点是另一个节点的祖先或孩子，以及两个节点没有直接或间接的父子关系。文章还提供了计算节点到根节点距离的三种方法：深度遍历方法（前序遍历）、回溯法（在list中）和回溯法（直接在path_list中）。

1）node1是node2的祖先节点或孩子结点，可以理解为两个节点在一条线上。例如：Dist(2,4),Dist(6,1)
2）node1和node2没有直接或间接的父子关系。例如，Dist(4,3)，他们需要一个共同的祖先结点1连接起来
假设lca是两个节点的最低公共祖先节点：leetcode 236
Dist(n1,n2)=Dist(root,n1)+Dist(root,n2)-2*Dist(root,lca)
求结点到根节点的距离

  
//深度遍历方法（前序遍历）
public void preOrder(TreeNode root, TreeNode node, int n) {
        if(root==null || root==node) return;
        preOrder(root.left,node,n+1);
        preOrder(root.right,node,n+1);
}
//回溯法 在list中
    public void getDistPath(TreeNode root, TreeNode node, List<TreeNode> path_list, List<List<TreeNode>> list) {
        if(root==null) return ;
        path_list.add(root);
        if(root==node) {
            list.add(new ArrayList<TreeNode>(path_list));
            return ;
        }else{
            getDistPath(root.left, node, path_list);
            getDistPath(root.right,node,path_list);
        }
        path_list.remove(path_list.size()-1);
        
    }
//回溯法 直接在path_list中
 public boolean getDistPath(TreeNode root, TreeNode node, List<TreeNode> path_list) {
        if(root==null) return false;
        path_list.add(root);
        if(root==node) return true;
        
        boolean found=false;
        //先去左子树找
        found=getDistPath(root.left, node, path_list);
        //左子树找不到去右子树找
        if(!found) found=getDistPath(root.right,node,path_list);
        //左右都找不到，弹出栈顶元素
        if(!found) path_list.remove(path_list.size()-1);
        
        return found;
    }