thinking

Get a binary tree problem , First ask yourself two questions ：
1、 Whether you can get the answer by traversing the binary tree ？ If possible , Use one traverse With external variables , This is called 「 Traverse 」 The mode of thinking .
2、 Whether a recursive function can be defined , Pass the subproblem （ subtree ） The answer to the original question ？ If possible , Write the definition of this recursive function , And make full use of the return value of this function , This is called 「 Break down the problem 」 The mode of thinking .
for example ： Calculate the maximum depth of the binary tree
1、 Ergodic thinking

//  Record the maximum depth 
int res = 0;
//  Record the depth of the node traversed 
int depth = 0;

//  The main function 
int maxDepth(TreeNode root) {
    
	traverse(root);
	return res;
}

//  Binary tree traversal framework 
void traverse(TreeNode root) {
    
	if (root == null) {
    
		return;
	}
	//  Preamble position 
	depth++;
    if (root.left == null && root.right == null) {
    
        //  To the leaf node , Update maximum depth 
		res = Math.max(res, depth);
    }
	traverse(root.left);
	traverse(root.right);
	//  Post sequence position 
	depth--;
}

2、 Break down the problem
On recursion , Learn to define .
Learn to look beyond the code , Make full use of definitions rather than sorting out recursive steps .

//  Definition ： Enter the root node , Returns the maximum depth of the binary tree 
int maxDepth(TreeNode root) {
    
	if (root == null) {
    
		return 0;
	}
	//  Using definitions , Calculate the maximum depth of the left and right subtrees 
	int leftMax = maxDepth(root.left);
	int rightMax = maxDepth(root.right);
	//  The maximum depth of the whole tree is equal to the maximum depth of the left and right subtrees, and the maximum value is taken ,
    //  Then add the root node itself 
	int res = Math.max(leftMax, rightMax) + 1;
	return res;
}