本篇文章给大家谈谈[LeetCode]654.MaximumBinaryTree_Mediumtag:stack，同时本文还将给你拓展654.MaximumBinaryTree、BinaryTreeM

本篇文章给大家谈谈[LeetCode] 654. Maximum Binary Tree_Medium tag: stack，同时本文还将给你拓展654. Maximum Binary Tree、Binary Tree Maximum Path Sum leetcode、Binary Tree Maximum Path Sum@LeetCode、LeetCode - Easy - 104. Maximum Depth of Binary Tree等相关知识，希望对各位有所帮助，不要忘了收藏本站喔。

• [LeetCode] 654. Maximum Binary Tree_Medium tag: stack
• 654. Maximum Binary Tree
• Binary Tree Maximum Path Sum leetcode
• Binary Tree Maximum Path Sum@LeetCode
• LeetCode - Easy - 104. Maximum Depth of Binary Tree

[LeetCode] 654. Maximum Binary Tree_Medium tag: stack

Input: [3,2,1,6,5]
Output: return the tree root node representing the following tree:

      6
    /      3     5
    \    / 
     2  0   
               1

# DeFinition for a binary tree node.
# class TreeNode:
#     def __init__(self,x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def constructMaximumBinaryTree(self,nums: List[int]) -> TreeNode:
        if not nums: return 
        def helper(nums,start,end):
            if start > end: return
            if start == end: 
            for index,num in enumerate(nums[start : end + 1],start):  #start from start
                if index == start or num > nums[maxIndex]:
                    maxIndex = index
            root = TreeNode(nums[maxIndex])
            root.left = helper(nums,maxIndex - 1)
            root.right = helper(nums,maxIndex + 1,end)
            return root
        return helper(nums,len(nums) - 1)

# DeFinition for a binary tree node.
# class TreeNode:
#     def __init__(self,nums: List[int]) -> TreeNode:
        if not nums: return
        stack,maxnum = [],max(nums)
        for num in (nums + [maxnum]):
　　　　　　　cur = TreeNode(num)
            while stack and stack[-1].val <= num: # in stack,is TreeNode
                node = stack.pop()
                if stack and stack[-1].val <= num:
                     stack[-1].right = node
                else:
                     cur.left = node
            stack.append(cur)
        return stack[0].left

654. Maximum Binary Tree

Input: [3,2,1,6,5]
Output: return the tree root node representing the following tree:

      6
    /      3     5
    \    / 
     2  0   
               1

 1 /**
 2  * DeFinition for a binary tree node.
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x),left(NULL),right(NULL) {}
 8  * };
 9  */
10 class Solution {
11 public:
12     TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
13         if (nums.size() == 0) return NULL;
14         if (nums.size() == 1) { 
15             TreeNode* node = new TreeNode(nums[0]);
16             return node;
17         }
18         int index = findMax(nums);
19         TreeNode* node = new TreeNode(nums[index]);
20         vector<int> left;
21         vector<int> right;
22         for(int i = 0; i < index; ++i) {
23             left.push_back(nums[i]);
24         }
25         for(int i = index + 1; i < nums.size(); ++i) {
26             right.push_back(nums[i]);
27         }
28         node->left = constructMaximumBinaryTree(left);
29         node->right = constructMaximumBinaryTree(right);
30         return node;
31     }
32     int findMax(const vector<int>& nums) {
33         if (nums.size() == 0) 
34             return -1;
35         int index = 0;
36         int max = nums[0];
37         for (int i = 0; i < nums.size(); ++i) {
38             if (nums[i] > max) {
39                 max = nums[i];
40                 index = i;
41             }    
42         }
43         return index;
44     }
45 };

Binary Tree Maximum Path Sum leetcode

Binary Tree Maximum Path Sum

Given a binary tree, find the maximum path sum.

For this problem, a path is defined as any sequence of nodes from some
starting node to any node in the tree along the parent-child
connections. The path does not need to go through the root.

For example: Given the below binary tree,

   1
  / \
 2   3 Return 6.

递归解法

思路

树的问题一般都用递归的解法, 递归结束条件为节点为空返回sum为0. 因为最大值处理为 root, root+ left , root + right 这三种情况还可能是root+ left + right, 所以维护一个数组来存储第四种情况的值(java无法按引用传，就只能建立一个数组）

复杂度

时间O(n) 空间栈O(logn)

代码

public int maxPathSum(TreeNode root) {
        int[] tem = new int[1];
        tem[0] = Integer.MIN_VALUE;
        helper(root, tem);
        return tem[0];
    }
public int helper(TreeNode root, int[] tem) {
        if (root == null) {
            return 0;
        }
        int left = helper(root.left, tem);
        int right = helper(root.right, tem);
        int max = Math.max(Math.max(root.val + left, root.val + right), root.val);
        tem[0] = Math.max(max, Math.max(root.val + left + right, tem[0]));
        return max;
    }

Binary Tree Maximum Path Sum@LeetCode

Binary Tree Maximum Path Sum

动态规划+深度优先搜索。把大问题（求整棵树的路径最大值）拆分成小问题（每颗子树的路径最大值），递推公式为：当前树的路径最大值=max(左子树的路径最大值, 右子树的路径最大值)+当前根节点的值。以此来推出最后全树的最大路径值。

实现代码：

javapublic class Solution {

    private int max;

    public int maxPathSum(TreeNode root) {
        if (root == null)
            return 0;
        max = root.val;
        traversal(root);
        return max;
    }

    private int traversal(TreeNode node) {
        int left = node.left == null ? 0 : traversal(node.left);
        int right = node.right == null ? 0 : traversal(node.right);
        left = left <= 0 ? 0 : left;
        right = right <= 0 ? 0 : right;
        max = Math.max(max, left + node.val + right);
        node.val = node.val + Math.max(left, right);
        return node.val;
    }
}

LeetCode - Easy - 104. Maximum Depth of Binary Tree

Topic

• Tree
• Depth-first Search
• Breadth-first Search
• Recursion

Description

https://leetcode.com/problems/maximum-depth-of-binary-tree/

Given the root of a binary tree, return its maximum depth.

A binary tree''s maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Example 1:

  3
 / \
9  20
  /  \
 15   7

Input: root = [3,9,20,null,null,15,7]
Output: 3

Example 2:

Input: root = [1,null,2]
Output: 2

Example 3:

Input: root = []
Output: 0

Example 4:

Input: root = [0]
Output: 1

Constraints:

• The number of nodes in the tree is in the range [0, 10⁴].
• -100 <= Node.val <= 10

Analysis

方法一：递归版

方法二：非递归版（DFS）

方法三：方法三：非递归版(BFS)

Submission

public class MaximumDepthOfBinaryTree {

	// 方法一：递归版(DFS)
	public int maxDepth1(TreeNode root) {
		if (root == null)
			return 0;
		return Math.max(maxDepth1(root.left), maxDepth1(root.right)) + 1;
	}

	// 方法二：非递归版(DFS)
	public int maxDepth2(TreeNode root) {
		if (root == null)
			return 0;

		int max = 1, count = 1;
		LinkedList<Object> stack = new LinkedList<>(Arrays.asList(root, max));
		TreeNode p = root;

		while (true) {
			if (p.left != null && p.right != null) {
				count++;
				stack.push(count);
				stack.push(p.right);
				p = p.left;
			} else if (p.left != null && p.right == null) {
				count++;
				p = p.left;
			} else if (p.left == null && p.right != null) {
				count++;
				p = p.right;
			} else {
				if (count > max)
					max = count;
				if (!stack.isEmpty()) {
					p = (TreeNode) stack.pop();
					count = (int) stack.pop();
				} else {
					break;
				}
			}
		}
		return max;
	}

	// 方法三：非递归版(BFS)
	public int maxDepth3(TreeNode root) {
		if (root == null)
			return 0;
		int count = 0;
		TreeNode p = root;

		LinkedList<TreeNode> queue = new LinkedList<TreeNode>(Arrays.asList(p));

		while (!queue.isEmpty()) {
			int size = queue.size();
			while (size-- > 0) {
				p = queue.poll();
				if (p.left != null) {
					queue.offer(p.left);
				}

				if (p.right != null) {
					queue.offer(p.right);
				}

			}
			count++;
		}

		return count;
	}

}

Test

import static org.junit.Assert.*;
import org.junit.Test;

import com.lun.util.BinaryTree.TreeNode;

public class MaximumDepthOfBinaryTreeTest {

	@Test
	public void test1() {
		MaximumDepthOfBinaryTree obj = new MaximumDepthOfBinaryTree();

		TreeNode root = new TreeNode(3);
		
		root.left = new TreeNode(9);
		root.right = new TreeNode(20);
		
		root.right.left = new TreeNode(15);
		root.right.right = new TreeNode(7);
		
		assertEquals(3, obj.maxDepth1(root));
		assertEquals(3, obj.maxDepth2(root));
		assertEquals(3, obj.maxDepth3(root));
	}
	
	@Test
	public void test2() {
		MaximumDepthOfBinaryTree obj = new MaximumDepthOfBinaryTree();
		TreeNode root = new TreeNode(1);		
		root.right = new TreeNode(2);
		
		assertEquals(2, obj.maxDepth1(root));
		assertEquals(2, obj.maxDepth2(root));
		assertEquals(2, obj.maxDepth3(root));
	}
	
	@Test
	public void test3() {
		MaximumDepthOfBinaryTree obj = new MaximumDepthOfBinaryTree();
		TreeNode root = null;
		
		assertEquals(0, obj.maxDepth1(root));
		assertEquals(0, obj.maxDepth2(root));
		assertEquals(0, obj.maxDepth3(root));
	}
	
	@Test
	public void test4() {
		MaximumDepthOfBinaryTree obj = new MaximumDepthOfBinaryTree();
		TreeNode root = new TreeNode(0);
		
		assertEquals(1, obj.maxDepth1(root));
		assertEquals(1, obj.maxDepth2(root));
		assertEquals(1, obj.maxDepth3(root));
	}
}

今天的关于[LeetCode] 654. Maximum Binary Tree_Medium tag: stack的分享已经结束，谢谢您的关注，如果想了解更多关于654. Maximum Binary Tree、Binary Tree Maximum Path Sum leetcode、Binary Tree Maximum Path Sum@LeetCode、LeetCode - Easy - 104. Maximum Depth of Binary Tree的相关知识，请在本站进行查询。