二叉树最长路径

╰+攻爆jí腚メ 2022-04-15 00:36 241阅读 0赞

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlYnR1NjY2_size_16_color_FFFFFF_t_70][]

分析：

暴力求每一段距离也可。

对于以本节点为根的二叉树，最远距离有三种可能：

1）最远路径来自左子树

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlYnR1NjY2_size_16_color_FFFFFF_t_70 1][]

2 ）最远路径来自右子树（图示与左子树同理）

3）最远路径为左右子树距离根最远的两个节点，经过根结点连起来。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlYnR1NjY2_size_16_color_FFFFFF_t_70 2][]（多种最长路径）

需要的信息：

1）左子树的最远路径长度

2）右子树的最远路径长度

3）左右子树的深度（深度即最远节点）

定义结点：

public static class Node {
    		public int value;
    		public Node left;
    		public Node right;
    
    		public Node(int data) {
    			this.value = data;
    		}
    	}

构造返回值信息：

public static class ReturnType{
    		public int maxDistance;//最长距离
    		public int h;          //高度
    		
    		public ReturnType(int m, int h) {
    			this.maxDistance = m;;
    			this.h = h;
    		}
    	}

求解过程比较好写了：

public static ReturnType process(Node head) {
    		if(head == null) {
    			return new ReturnType(0,0);
    		}
    		//收信息
    		ReturnType leftReturnType = process(head.left);
    		ReturnType rightReturnType = process(head.right);
    		
    		int includeHeadDistance = leftReturnType.h + 1 + rightReturnType.h;//情况3
    		int p1 = leftReturnType.maxDistance;
    		int p2 = rightReturnType.maxDistance;
    		
    		int resultDistance = Math.max(Math.max(p1, p2), includeHeadDistance);//最长距离
    		int hitself  = Math.max(leftReturnType.h, leftReturnType.h) + 1;     //树的高度等于子树高度+1
    		
    		return new ReturnType(resultDistance, hitself);
    	}

优化：

其实我们不需要返回左右子树深度，可以用一个全局变量记录。遇到NULL把变量记为0，不影响接下来的计算。

用一个含一个元素的数组来记录。因为某些二叉树题目不只需要一个信息，所以要利用全局数组。

public static int posOrder(Node head, int[] record) {
    		if (head == null) {
    			record[0] = 0;//重要
    			return 0;
    		}
    		//取信息
    		int lMax = posOrder(head.left, record);
    		int maxfromLeft = record[0];
    		int rMax = posOrder(head.right, record);
    		int maxFromRight = record[0];
    		
    		int curNodeMax = maxfromLeft + maxFromRight + 1;//情况3
    		record[0] = Math.max(maxfromLeft, maxFromRight) + 1;
    		
    		return Math.max(Math.max(lMax, rMax), curNodeMax);
    	}

最后放上全部代码：

package q;
    
    public class Demo {
    
    	public static class Node {
    		public int value;
    		public Node left;
    		public Node right;
    
    		public Node(int data) {
    			this.value = data;
    		}
    	}
    
    	public static int maxDistance(Node head) {
    		int[] record = new int[1];
    		return posOrder(head, record);
    	}
    	
    	public static class ReturnType{
    		public int maxDistance;//最长距离
    		public int h;          //高度
    		
    		public ReturnType(int m, int h) {
    			this.maxDistance = m;;
    			this.h = h;
    		}
    	}
    	
    	public static ReturnType process(Node head) {
    		if(head == null) {
    			return new ReturnType(0,0);
    		}
    		//收信息
    		ReturnType leftReturnType = process(head.left);
    		ReturnType rightReturnType = process(head.right);
    		
    		int includeHeadDistance = leftReturnType.h + 1 + rightReturnType.h;//情况3
    		int p1 = leftReturnType.maxDistance;
    		int p2 = rightReturnType.maxDistance;
    		
    		int resultDistance = Math.max(Math.max(p1, p2), includeHeadDistance);//最长距离
    		int hitself  = Math.max(leftReturnType.h, leftReturnType.h) + 1;     //树的高度等于子树高度+1
    		
    		return new ReturnType(resultDistance, hitself);
    	}
    
    	public static int posOrder(Node head, int[] record) {
    		if (head == null) {
    			record[0] = 0;//重要
    			return 0;
    		}
    		//取信息
    		int lMax = posOrder(head.left, record);
    		int maxfromLeft = record[0];
    		int rMax = posOrder(head.right, record);
    		int maxFromRight = record[0];
    		
    		int curNodeMax = maxfromLeft + maxFromRight + 1;//情况3
    		record[0] = Math.max(maxfromLeft, maxFromRight) + 1;
    		
    		return Math.max(Math.max(lMax, rMax), curNodeMax);
    	}
    
    	public static void main(String[] args) {
    		Node head1 = new Node(1);
    		head1.left = new Node(2);
    		head1.right = new Node(3);
    		head1.left.left = new Node(4);
    		head1.left.right = new Node(5);
    		head1.right.left = new Node(6);
    		head1.right.right = new Node(7);
    		head1.left.left.left = new Node(8);
    		head1.right.left.right = new Node(9);
    		System.out.println(maxDistance(head1));
    
    		Node head2 = new Node(1);
    		head2.left = new Node(2);
    		head2.right = new Node(3);
    		head2.right.left = new Node(4);
    		head2.right.right = new Node(5);
    		head2.right.left.left = new Node(6);
    		head2.right.right.right = new Node(7);
    		head2.right.left.left.left = new Node(8);
    		head2.right.right.right.right = new Node(9);
    		System.out.println(maxDistance(head2));
    
    	}
    
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlYnR1NjY2_size_16_color_FFFFFF_t_70]: /images/20220415/a0c8d85930a8413ca3bd9b7444145512.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlYnR1NjY2_size_16_color_FFFFFF_t_70 1]: /images/20220415/77a28fa4d21c4de28527030054d0f152.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlYnR1NjY2_size_16_color_FFFFFF_t_70 2]: /images/20220415/53f86aac81334fffab7bbc3b22d82b25.png