二叉树|173. 二叉搜索树迭代器 129. 求根节点到叶节点数字之和

本文主要是介绍二叉树|173. 二叉搜索树迭代器 129. 求根节点到叶节点数字之和，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

173. 二叉搜索树迭代器

实现一个二叉搜索树迭代器类BSTIterator ，表示一个按中序遍历二叉搜索树（BST）的迭代器：
BSTIterator(TreeNode root) 初始化 BSTIterator 类的一个对象。BST 的根节点 root 会作为构造函数的一部分给出。指针应初始化为一个不存在于 BST 中的数字，且该数字小于 BST 中的任何元素。
boolean hasNext() 如果向指针右侧遍历存在数字，则返回 true ；否则返回 false 。
int next()将指针向右移动，然后返回指针处的数字。
题目链接： 173. 二叉搜索树迭代器
解题思路：用null标记下一个输出处理的left变为null

class BSTIterator {private Stack<TreeNode> nodeStack;private TreeNode point;public BSTIterator(TreeNode root) {nodeStack = new Stack<>();nodeStack.push(root);// point.right=nodeStack.top();}public int next() {while(!nodeStack.isEmpty()){if(nodeStack.peek()==null){nodeStack.pop();return nodeStack.pop().val;}TreeNode node=nodeStack.pop();if(node.right!=null){nodeStack.push(node.right);}nodeStack.push(node);nodeStack.push(null);while(node.left!=null){nodeStack.push(node.left);TreeNode tmp=node.left;node.left=node.left.left;tmp.left=null;}  }return -1;}public boolean hasNext() {if(!nodeStack.isEmpty()){return true;}else{return false;}}
}

129. 求根节点到叶节点数字之和

题目： 给你一个二叉树的根节点 root ，树中每个节点都存放有一个 0 到 9 之间的数字。
每条从根节点到叶节点的路径都代表一个数字：
例如，从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123 。
计算从根节点到叶节点生成的所有数字之和。
叶节点是指没有子节点的节点。
题目链接： 129. 求根节点到叶节点数字之和
解题思路： 从上往下遍历

    class Solution {public int sumNumbers(TreeNode root) {return dfs(root, 0);}public int dfs(TreeNode root, int prevSum) {if (root == null) {return 0;}int sum = prevSum * 10 + root.val;if (root.left == null && root.right == null) {return sum;} else {return dfs(root.left, sum) + dfs(root.right, sum);}}}