lintcode,二叉树的最大深度

admin管理员组

文章数量:1794759

lintcode,二叉树的最大深度

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的距离。

解题思路：递归解乏就是判断左右子树最大深度哪一个更大。还可以用两个栈分别存储节点和节点所在深度，只要节点栈不为空，就取出深度判断是否更大，然后将左右孩子节点放进节点栈和节点深度栈。
一刷ac。二刷ac

/*** Definition of TreeNode:* public class TreeNode {*     public int val;*     public TreeNode left, right;*     public TreeNode(int val) {*         this.val = val;*         this.left = this.right = null;*     }* }*/
public class Solution {/*** @param root: The root of binary tree.* @return: An integer.*/public int maxDepth(TreeNode root) {if(root == null) return 0;return Math.max(maxDepth(root.left), maxDepth(root.right))+1;}
}

/*** Definition of TreeNode:* public class TreeNode {*     public int val;*     public TreeNode left, right;*     public TreeNode(int val) {*         this.val = val;*         this.left = this.right = null;*     }* }*/
public class Solution {/*** @param root: The root of binary tree.* @return: An integer.*/public int maxDepth(TreeNode root) {if(root == null) return 0;Stack<TreeNode> nodestack = new Stack<TreeNode>();Stack<Integer> depthstack = new Stack<Integer>();int maxdepth = 1;nodestack.push(root);depthstack.push(maxdepth);while(!nodestack.isEmpty()){TreeNode node = nodestack.pop();int d = depthstack.pop();if(d > maxdepth) maxdepth = d;if(node.left != null){nodestack.push(node.left);depthstack.push(d+1);}if(node.right != null){nodestack.push(node.right);depthstack.push(d+1);}}return maxdepth;}
}

本文标签： LintCode二叉树的最大深度